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

ランダムポインタを持つリンクリストとは

リンクリスト(連結リスト)は代表的な線形データ構造の一つで、各ノードは「ノードが保持する値(データ)」と「次のノードのアドレスを格納するポインタ(next)」という2つの部分で構成されます。

本記事では、さらに各ノードがリスト内の別のノードを指す「ランダムポインタ(random)」を持つリンクリストを扱います。このようなリストに対して、元のリストと同じデータ・同じランダムポインタ構造を持つ新しいリストを作成することを、リンクリストの「ディープコピー(Deep Copy)」と呼びます。

例

入力:

出力:

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

解説: 元のリストの各ノードの直後に同じ値を持つ複製ノードを挿入し、複製ノードのランダムポインタを正しく張り替えたうえで新旧のノードを分離すると、5-> 2-> 3-> 7-> 4-> という完全なコピーが得られます。

問題を解くためのアプローチ

データとランダムポインタを持つリンクリストのコピーを作るには、次の3段階の手順が有効です。ポイントは、ハッシュマップなどの補助データ構造を使わず、元のリストの中間に複製ノードを挟み込むことで、追加メモリをO(1)に抑えられる点です。

1. 複製ノードの挿入: 元のリストの各ノードの直後に、同じ値を持つ新しいノードを挿入し、元ノードと複製ノードが交互に並ぶ状態を作ります。
2. ランダムポインタの設定: 元のノードのランダムポインタの参照先をたどり、その「次」(= 参照先ノードの複製)を、複製ノードのランダムポインタとして設定します(curr->next->random = curr->random->next)。
3. リストの分離: 交互に並んだ元ノードと複製ノードのリンクを付け替えて2つの独立したリストに分離すれば、ディープコピーの完成です。

アルゴリズムの手順

• データフィールドとランダムノードへのポインタを持つリンクリストを用意します。
• 関数 copyRandomList(listnode* head) は、元のリストの先頭ノードを引数に受け取り、ディープコピーされたリストを返します。
• 先頭ノードがNULL(空のリスト)の場合は、そのままheadを返します。
• 元のリストの各ノードの後ろに、同じ値を持つ新しいノードを挿入します。
• 元のリストからランダムポインタの情報を読み取り、新しく挿入したノードに対応するランダムポインタを設定します。
• すべての複製ノードのデータとポインタが整ったら、リストを分離し、コピー済みのリストを結果として返します。

C++での実装例

#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;
    }
    // 元のリストの各ノードの後ろに、同じ値を持つ新しいノードを挿入する
    listnode * curr = head;
    while (curr) {
        listnode * newHead = new listnode(curr -> data);
        newHead -> next = curr -> next;
        curr -> next = newHead;
        curr = curr -> next -> next;
    }
    // 新しく作成したノードにランダムポインタを設定する
    curr = head;
    while (curr) {
        if (curr -> random)
            (curr -> next) -> random = (curr -> random) -> next;
        curr = curr -> next -> next;
    }
    // 新しく作成したリストを元のリストから分離する
    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

出力の各行は「ノードの値 ランダムポインタが指すノードの値」を表しています。元のリストとディープコピーしたリストの出力が完全に一致していることから、データだけでなくランダムポインタの構造まで正しく複製できていることが分かります。この手法では複製ノードを元のリストに一時的に挟み込むことで、ハッシュマップ不要・追加メモリO(1)・計算量O(N)でディープコピーを実現できます。