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

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

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

例

入力-1：

出力：

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

説明：

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

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

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

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

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

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

例

class listnode:
   def __init__(self, data):
      self.data = data
      self.next = None
      self.random = None
def copyRandomList(head):
   if head is None:
      return head
   # Insert a new node with the same value after each node in the original list.
   curr = head
   while curr != None:
      new = listnode(curr.data)
      new.next = curr.next
      curr.next = new
      curr = curr.next.next

   # Now place the randompointer with the newly created node.
   curr = head
   while curr != None:
      curr.next.random = curr.random.next
      curr = curr.next.next

   # Now Let us separate the newly created list from the original list.
   curr = head
   temp = head.next
   while curr.next != None:
      dummyHead = curr.next
      curr.next = curr.next.next
      curr = dummyHead
   return temp
def printList(head):
   curr = head
   while curr != None:
      print(curr.data, " ", curr.random.data)
      curr = curr.next
head = listnode(1)
head.next = listnode(2)
head.next.next = listnode(3)
head.next.next.next = listnode(4)
head.next.next.next.next = listnode(5)
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
print("Original list:\n")
printList(head)
copiedList = copyRandomList(head)
print("\n Deep Copy of the List:")
printList(copiedList)

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

出力

Original list:
1 3
2 1
3 5
4 5
5 2
Deep Copy of the List:
1 3
2 1
3 5
4 5
5 2