C++でリンクリストを交互に分割するための再帰的アプローチ

入力として単一リンクリストが与えられます。目標は、リストを、元のリストの代替ノードを持つ2つの単一リンクリストに分割することです。入力リストにノードa→b→c→d→e→fがある場合、分割後、2つのサブリストはa→c→eとb→d→fになります。

2つのポインタN1とN2を取ります。1つは元のリストの先頭を指し、もう1つは先頭→次を指します。次に、両方のポインタを次のノードに移動し、サブリストを作成します。

例

入力 −リスト：-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から開始し、次のポイントで代替ノードを指定して、上記のサブリストを作成します。

入力 −リスト：-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つのポインターN1とN2を使用します。1つは元のリストの先頭を指し、もう1つは先頭→次を指します。次に、両方のポインタを次のノードに移動し、サブリストを作成します。

• intデータ部分とノードを次のポインタとして持つ構造体ノードを取ります。

• 関数addtohead（Node ** head、int data）は、ノードをヘッドに追加して、単一リンクリストを作成するために使用されます。

• 上記の関数を使用して、最初のノードへのポインタとしてheadを使用して、単一リンクリストを作成します。

• 関数display（Node * head）は、ヘッドノードから始まるリンクリストを印刷するために使用されます。

• 2つのノードポインタnode1とnode2を取ります。

• 関数splitList（Node * head、Node ** n1、Node ** n2）は、ノードポインターを受け取り、n1をheadに、n2をhead→元の文字列の次の位置にポイントします。

• その中で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;

  に設定します。

• fN2→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