C++でランダムポインタを使用してリストをコピーする

リンクリストは線形データ構造であり、各ノードには2つのブロックがあり、一方のブロックにはノードの値またはデータが含まれ、もう一方のブロックには次のフィールドのアドレスが含まれます。

各ノードにリスト内の他のノードを指すランダムポインタが含まれるようなリンクリストがあると仮定します。タスクは、元のリストと同じリストを作成することです。ランダムなポインタを持つ元のリストからリストをコピーすることを、リンクリストの「ディープコピー」と呼びます。

例

入力-1

出力：

5-> 2 -> 3 -> 7 ->4 ->

説明： 指定されたリンクリスト内の元のノードの値を新しいリストに追加し、元のリンクリストのランダムポインタを新しいリスト内の次のノードに置き換えると、5->2->3->になります。 7-> 4->

この問題を解決するためのアプローチ

データとランダムポインタを含むノードを含むリンクリストがあります。データとランダムポインタを使用してリンクリストのコピーを作成するために、最初に各ノードの後に​​同じ値で新しいノードを追加します。これにより、各ノードの後に​​重複ノードが作成されます。

初期化後、リスト内のランダムポインターのパスを確認し、それに応じてランダムポインターを新しく作成されたノードに配置します。

元のリストの各ノードの後に​​新しく作成されたノードを分離すると、リンクリストのディープコピーが作成されます。

• データフィールドとそのランダムノードのアドレスへのポインタを含むリンクリストを作成します。
• 関数copyRandomList（listnode * head）は、元のリストのヘッドノードを入力として受け取り、リストのディープコピーを返します。
• ヘッドが空の場合、リストは空であり、ヘッドも返す必要があります。
• ここで、元のリストの各ノードの後に​​同じ値の新しいノードを挿入します。
• 次に、元のリストからランダムポインターをコピーし、新しいノードを挿入します。つまり、newnode-> next =curr-> randomPointer
• ポインタとデータを使用して新しいノードが作成されたら、リストを分離し、リストを出力として返します。

例

#include <bits/stdc++.h>
using namespace std;
struct listnode {
   int data;
   listnode * next, * random;
   listnode(int d) {
      data = d;
      next = NULL;
      random = NULL;
   }
};
void print(listnode * head) {
   listnode * curr = head;
   while (curr) {
      cout << curr -> data << " " << curr -> random -> data << endl;
      curr = curr -> next;
   }
}
listnode * copyRandomList(listnode * head) {
   if (!head) {
      return head;
   }
   //Insert a new node with the same value after each node in the original list.
   listnode * curr = head;
   while (curr) {
      listnode * newHead = new listnode(curr -> data);
      newHead -> next = curr -> next;
      curr -> next = newHead;
      curr = curr -> next -> next;
   }
   //Now place the randompointer with the newly created node.
   curr = head;
   while (curr) {
      if (curr -> random)
         (curr -> next) -> random = (curr -> random) -> next;
      curr = curr -> next -> next;
   }
   //Now Let us separate the newly created list
   curr = head;
   listnode * result = curr -> next;
   listnode * dummyHead = new listnode(-1);
   dummyHead -> next = result;
   while (curr) {
      curr -> next = result -> next;
      curr = curr -> next;

      if (curr) {
         result -> next = curr -> next;
      }
      result = result -> next;
   }
   result = dummyHead -> next;
   delete dummyHead;
   return result;
}
int main() {
   listnode * head = new listnode(5);
   head -> next = new listnode(6);
   head -> next -> next = new listnode(3);
   head -> next -> next -> next = new listnode(4);
   head -> next -> next -> next -> next = new listnode(2);
   head -> random = head -> next -> next;
   head -> next -> random = head;
   head -> next -> next -> random =
      head -> next -> next -> next -> next;
   head -> next -> next -> next -> random =
      head -> next -> next -> next -> next;
   head -> next -> next -> next -> next -> random =
      head -> next;
   cout << "Original list :" << endl;
   print(head);
   cout << "Deep Copy of the List:" << endl;
   listnode * deep_copyList = copyRandomList(head);
   print(deep_copyList);
   return 0;
}

上記のコードを実行すると、次のように出力が生成されます

出力

Original List:
5 3
6 5
3 2
4 2
2 6
Deep Copy of the List:
5 3
6 5
3 2
4 2
2 6