C++で連結リストを交互に2つのリストへ分割する再帰的アプローチ

片方向連結リストが入力として与えられたとき、元のリストのノードを交互に振り分けた2つの片方向連結リストに分割することを目標とします。例えば、入力リストのノードが a → b → c → d → e → f という並びである場合、分割後の2つのサブリストは「a → c → e」と「b → d → f」になります。

この問題では、2つのポインタ N1 と N2 を用意します。N1 は元のリストの先頭ノードを、N2 は先頭の次のノードを指すようにします。その後、両方のポインタを「次の次」のノードへ順に移動させながら、それぞれのサブリストを構築していきます。

具体例

入力 − リスト: 1 → 5 → 7 → 12 → 2 → 96 → 33

出力 −
元のリスト: 1 5 7 12 2 96 33
リスト1: 1 7 2 33
リスト2: 5 12 96

解説 − 先頭の 1 と 5 から処理を開始し、交互のノードをたどることで上記の2つのサブリストを作成します。

入力 − リスト: 13 → 53 → 90 → 18 → 44 → 11 → 99 → 32

出力 −
元のリスト: 13 53 90 18 44 11 99 32
リスト1: 13 90 44 99
リスト2: 53 18 11 32

解説 − 先頭の 13 と 53 から処理を開始し、交互のノードをたどることで上記の2つのサブリストを作成します。

プログラムで使用するアプローチ

このアプローチでも、2つのポインタ N1 と N2 を用意し、一方は元のリストの先頭を、もう一方は先頭の次のノードを指すようにします。その後、両方のポインタを「次の次」のノードへ移動させながらサブリストを作成します。具体的な手順は以下のとおりです。

• int 型のデータ部分と、次ノードへのポインタ next を持つ構造体 Node を定義します。
• 関数 addtohead(Node** head, int data) は、リストの先頭にノードを追加して片方向連結リストを構築するために使用します。
• 上記の関数を使い、head を先頭ノードへのポインタとして片方向連結リストを作成します。
• 関数 display(Node* head) は、先頭ノードから順にリンクリストの内容を出力するために使用します。
• 2つの Node ポインタ node1 と node2 を用意します。
• 関数 splitList(Node* head, Node** n1, Node** n2) はノードポインタを受け取り、n1 を元のリストの先頭に、n2 を先頭の次のノードに設定します。
• その内部で split(*n1, *n2) を呼び出し、元のリストを2つのサブリストに分割します。
• 関数 split(Node* N1, Node* N2) は N1 と N2 のポインタを受け取り、元のリストの交互のノードを含む2つのサブリストを作成します。
• N1 と N2 のどちらかが NULL の場合は、何もせずに処理を終了します。
• N1→next が NULL でない場合、tmp = N1->next->next として N1->next = tmp を設定します。
• N2→next が NULL でない場合も同様に、tmp = N2->next->next として N2->next = tmp を設定します。
• split(N1->next, N2->next); を呼び出して、次のノードペアの処理へ再帰的に進みます。
• 最後に display() を使って、分割後のサブリストを出力します。

実装例

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
};
void addtohead(Node** head, int data){
   Node* nodex = new Node;
   nodex->data = data;
   nodex->next = (*head);
   (*head) = nodex;
}
void split(Node* N1, Node* N2){
   Node *tmp;
   if (N1 == NULL || N2 == NULL){
      return;
   }
   if (N1->next != NULL){
      tmp=N1->next->next;
      N1->next = tmp;
   }
   if (N2->next != NULL){
      tmp=N2->next->next;
      N2->next = tmp;
   }
   split(N1->next, N2->next);
}
void splitList(Node* head, Node** n1, Node** n2){
   *n1 = head;
   *n2 = head->next;
   split(*n1, *n2);
}
void display(Node* head){
   Node* curr = head;
   if (curr != NULL){
      cout<<curr->data<<" ";
      display(curr->next);
   }
}
int main(){
   Node* head = NULL;
   Node *node1 = NULL, *node2 = NULL;
   addtohead(&head, 20);
   addtohead(&head, 12);
   addtohead(&head, 15);
   addtohead(&head, 8);
   addtohead(&head, 10);
   addtohead(&head, 4);
   addtohead(&head, 5);

   cout<<"Original List :"<<endl;
   display(head);
   splitList(head, &node1, &node2);
   cout<<endl<<"List 1: ";
   display(node1);
   cout<<endl<<"List 2: ";
   display(node2);
   return 0;
}

出力結果

上記のコードを実行すると、次のような出力が得られます。

Original List :
5 4 10 8 15 12 20
List 1: 5 10 15 20
List 2: 4 8 12