Pythonでランダムポインタを持つ連結リストをディープコピーする方法

連結リスト(Linked List)は線形データ構造の一種で、各ノードが2つの要素で構成されています。1つはノードの値(データ)を格納する部分、もう1つは次のノードのアドレスを指すポインタです。

ここでは、各ノードがリスト内の他のノードを指す「ランダムポインタ」を持つ連結リストを想定します。このリストと全く同じ構造を持つ新しいリストを構築するのが課題です。ランダムポインタを持つ元のリストから完全な複製を作成することを、連結リストの「ディープコピー」と呼びます。

具体例

入力:

元の連結リスト: 1 → 2 → 3 → 4 → 5(各ノードはランダムポインタで他のノードを指しています)

出力:

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

解説:

元のノードの値を持つ新しいノードを連結し、元のリストのランダムポインタの指す先を新しいリスト側に対応付けることで、5→2→3→7→4→という同じ構造のコピーが得られます。

この問題へのアプローチ

データとランダムポインタを持つ連結リストをコピーするには、まず各ノードの直後に同じ値を持つ新しいノードを挿入します。これにより、各ノードの後に複製ノードが並ぶ状態になります。

次に、元のリストにおけるランダムポインタの経路を確認し、新しく作成したノードにも対応するランダムポインタを設定します。

最後に、元のリストから新しく作成したノード群を分離すれば、連結リストのディープコピーが完成します。

アルゴリズムの手順

• データフィールドとランダムノードへのポインタを持つ連結リストを用意します。
• 関数 copyRandomList(head) は、元のリストの先頭ノードを入力として受け取り、リストのディープコピーを返します。
• head が空の場合、リストも空なのでそのまま 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

    # 元のリストの各ノードの直後に、同じ値を持つ新しいノードを挿入する
    curr = head
    while curr != None:
        new = listnode(curr.data)
        new.next = curr.next
        curr.next = new
        curr = curr.next.next

    # 新しく作成したノードにランダムポインタを設定する
    curr = head
    while curr != None:
        curr.next.random = curr.random.next
        curr = curr.next.next

    # 新しく作成したリストを元のリストから分離する
    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

このように、O(n) の時間計算量・追加のハッシュマップ不要で、元のリストと完全に同じデータおよびランダムポインタ構造を持つディープコピーを作成できることが確認できます。この手法は、追加領域を最小限に抑えながらランダムポインタ付きリストを複製する効率的なアプローチとして知られています。