138. Copy List with Random Pointer

題目 / Problem

中文： 給你一個長度為 n 的鏈結串列，除了普通的 next 指標外，每個節點還有一個 random 指標，它可以指向串列中的任何節點，或者指向 null。請你建立這個串列的深拷貝（deep copy）：新串列必須由 n 個全新的節點組成，每個新節點的值和對應的舊節點相同，而且新節點的 next 與 random 都只能指向新串列裡的節點，不能指向任何舊節點。最後回傳新串列的頭節點。

English: You are given a linked list of length n. In addition to the usual next pointer, each node has a random pointer that can point to any node in the list or to null. Build a deep copy: the new list must consist of n brand-new nodes whose values match the originals, and every next / random pointer in the new list must point only to nodes in the new list, never to an original node. Return the head of the copied list.

輸入/輸出格式 / I-O format: 每個節點以 [val, random_index] 表示，random_index 是 random 指向的節點下標（0 到 n-1），或 null。你的函式只會收到 head。

約束 / Constraints: - 0 <= n <= 1000 - -10^4 <= Node.val <= 10^4 - Node.random 是 null，或指向串列中的某個節點。

範例 / Example 1:

Input:  head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

串列是 7 → 13 → 11 → 10 → 1；其中 13.random → 7、11.random → 1、10.random → 11、1.random → 7、7.random → null。

名詞解釋 / Glossary

• 鏈結串列 / Linked list： 一串節點，每個節點存一個值和一個指向下一個節點的指標 next。最後一個節點的 next 是 null。
• 深拷貝 / Deep copy： 複製出一組全新的節點，新舊之間完全獨立；修改新串列不會影響舊串列。相對地，「淺拷貝」只是複製指標、仍共用同一批節點。
• 指標 / Pointer： 一個存著「某節點記憶體位址」的變數。p->next 表示「順著 p 走到它指的節點，再取那個節點的 next 欄位」。
• 雜湊表 / Hash map： 一種能以近乎 O(1) 時間做「鍵 → 值」查找的容器。這裡我們用它記錄「舊節點 → 新節點」的對應關係。C++ 中是 unordered_map。
• 原地交錯 / In-place interweaving： 一種省空間技巧：把每個新節點直接插在對應舊節點的後面，形成 A → A' → B → B' → …，利用這個結構就不需要額外的雜湊表。
• 時間/空間複雜度 / Time & space complexity： 用 O(...) 描述執行時間與額外記憶體隨輸入規模 n 增長的趨勢。
• malloc / free： C 語言中手動向系統要一塊記憶體（malloc）與歸還記憶體的方式；LeetCode 會負責釋放你回傳的節點，所以這題我們只 malloc 不 free。

思路

中文： 這題的難點在於 random 指標：當我們一邊走一邊複製節點時，某個節點的 random 可能指向一個「我們還沒建立出來」的節點，所以沒辦法直接接上。最直覺的暴力／雜湊表做法分兩趟：第一趟只複製值、把每個舊節點對應到一個新節點，存進雜湊表 舊 → 新；第二趟再走一遍，對每個舊節點 cur，用雜湊表查出 cur->next 和 cur->random 各自對應的新節點，接到新節點上。因為所有新節點在第一趟就都造好了，第二趟查表一定查得到。這個方法簡單好懂，時間 O(n)、但要額外 O(n) 的雜湊表空間。

我們可以更聰明，做到 O(1) 額外空間的原地交錯法，分三趟：第一趟，把每個新節點 A' 直接插在舊節點 A 後面，串成 A → A' → B → B' → …。這一步的巧妙之處是：現在任何舊節點 X 的新副本，就正好是 X->next。第二趟設定 random：對每個舊節點 X，若 X->random 指向 Y，那麼 X 的副本（X->next）的 random 就該指向 Y 的副本，也就是 Y->next，於是一行 X->next->random = X->random->next 就搞定，不需要查表——交錯結構本身就是我們的「對照表」。第三趟把兩條串列拆開，還原舊串列並抽出新串列。關鍵不變量：在第二趟之前，每個舊節點的 next 一定緊跟著它自己的副本，這保證了 ->next 就是「查表」。

English: The tricky part is the random pointer: while copying nodes one by one, a node's random may point to a node we haven't created yet, so we can't wire it up on the spot. The straightforward brute-force / hash-map solution uses two passes. Pass 1: create a new node for every old node (values only) and store the pairing old → new in a hash map. Pass 2: walk again, and for each old node cur look up which new nodes correspond to cur->next and cur->random, then attach them to cur's copy. Since every new node already exists after pass 1, every lookup succeeds. It's simple and runs in O(n) time, but costs O(n) extra space for the map.

We can do better — O(1) extra space — with in-place interweaving in three passes. Pass 1: splice each new node A' right after its original A, producing A → A' → B → B' → …. The beauty: now the copy of any old node X is exactly X->next. Pass 2 sets random: if X->random points to Y, then X's copy (X->next) must point its random to Y's copy (Y->next), so the single line X->next->random = X->random->next does it — no map needed, because the interweaved structure is the lookup table. Pass 3 unzips the two lists, restoring the original and extracting the copy. Key invariant: before pass 2, every old node's next is its own fresh copy — that's what makes ->next act as the lookup.

逐步走查 / Walkthrough

以 Example 1 為例，原串列 7 → 13 → 11 → 10 → 1，random 關係：13→7, 11→1, 10→11, 1→7, 7→null。我們追蹤原地交錯法。

Pass 1 — 交錯插入副本 / Interweave copies:

Pass 2 — 設定 random（cur->next->random = cur->random->next）/ Wire up random:

Pass 3 — 拆開兩條串列 / Unzip: 把奇數位（舊）與偶數位（新）分開，還原 7 → 13 → 11 → 10 → 1，並回傳新串列頭 7'。新串列 7' → 13' → 11' → 10' → 1' 的 random 完全對應舊串列，且不指向任何舊節點。✅

Solution — C

/*
 * 原地交錯法 / In-place interweaving (O(1) extra space):
 *   1) 把每個新節點插在對應舊節點後面：A → A' → B → B' → …
 *      Splice each copy right after its original.
 *   2) 利用 cur->next 就是副本這點來接 random。
 *      Use "the copy sits at cur->next" to set random pointers.
 *   3) 把交錯串列拆回舊串列 + 新串列。 Unzip into two lists.
 */

// LeetCode 已定義 struct Node { int val; struct Node *next; struct Node *random; };
// LeetCode already provides the Node definition above the function.

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL) return NULL;              // 空串列直接回傳 null / empty list → null

    // ---- Pass 1: 交錯插入副本 / interweave copies ----
    struct Node* cur = head;                    // cur 指向目前的舊節點 / current old node
    while (cur != NULL) {                        // 走遍每個舊節點 / visit every old node
        // malloc 向系統要一塊 Node 大小的記憶體 / malloc grabs memory for one Node
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;                    // 複製值 / copy the value
        copy->next = cur->next;                  // 副本接到 cur 原本的下一個 / copy points to cur's old next
        copy->random = NULL;                     // random 之後才設，先清空 / clear random for now
        cur->next = copy;                        // 把副本插在 cur 後面 / insert copy right after cur
        cur = copy->next;                        // 跳過副本，走到下一個舊節點 / skip copy → next old node
    }

    // ---- Pass 2: 設定 random / assign random pointers ----
    cur = head;                                  // 從頭再走一次 / restart from head
    while (cur != NULL) {                         // cur 一律停在舊節點上 / cur always on an old node
        if (cur->random != NULL)                 // 舊節點有 random 才需要處理 / only if random exists
            // cur->next 是 cur 的副本；cur->random->next 是目標的副本
            // cur->next is cur's copy; cur->random->next is the target's copy
            cur->next->random = cur->random->next;
        cur = cur->next->next;                    // 跳過副本，前進到下一個舊節點 / advance two steps
    }

    // ---- Pass 3: 拆開兩條串列 / separate the two lists ----
    cur = head;                                  // 再次從頭 / restart from head
    struct Node* newHead = head->next;           // 新串列的頭就是第一個副本 / new head = first copy
    while (cur != NULL) {                          // 逐一還原並抽出 / restore & extract node by node
        struct Node* copy = cur->next;           // copy 是 cur 的副本 / copy is cur's clone
        cur->next = copy->next;                   // 舊節點跳過副本，接回原本的下一個舊節點 / relink old list
        if (copy->next != NULL)                   // 若後面還有節點 / if a next old node exists
            copy->next = copy->next->next;        // 副本也跳過一個舊節點，接到下一個副本 / relink new list
        cur = cur->next;                          // 前進到下一個舊節點 / move to next old node
    }

    return newHead;                              // 回傳新串列的頭 / return head of the copy
}

Solution — C++

/*
 * 雜湊表法 / Hash-map approach (O(n) time, O(n) space):
 *   Pass 1: 為每個舊節點造一個新節點，存進 unordered_map<舊, 新>。
 *           Create a copy per old node; remember old→new in a map.
 *   Pass 2: 用查表把新節點的 next 與 random 接好。
 *           Use the map to wire each copy's next and random.
 * 這個版本比原地交錯更好讀，很適合初學者理解問題本質。
 * Easier to read than interweaving — great for grasping the core idea.
 */

// LeetCode 已定義 class Node { int val; Node* next; Node* random; ... };
// LeetCode already provides the Node class.

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // unordered_map 是雜湊表，查找/插入平均 O(1)。鍵是舊節點指標，值是新節點指標。
        // unordered_map = hash table with average O(1) ops; key = old ptr, value = new ptr.
        unordered_map<Node*, Node*> map;

        // ---- Pass 1: 只複製值，建立對應關係 / copy values, build the mapping ----
        for (Node* cur = head; cur != nullptr; cur = cur->next)  // range 太麻煩，手動走串列 / manual walk
            map[cur] = new Node(cur->val);       // new 動態配置一個新節點 / new allocates one node

        // ---- Pass 2: 接好 next 與 random / wire next and random ----
        for (Node* cur = head; cur != nullptr; cur = cur->next) {
            // 小技巧：map[nullptr] 會回傳預設值 nullptr，所以尾端與空 random 自動處理正確。
            // Trick: map[nullptr] yields the default nullptr, so tail / null-random just work.
            map[cur]->next   = map[cur->next];   // 新節點的 next = 舊 next 對應的新節點 / copy's next
            map[cur]->random = map[cur->random]; // 新節點的 random = 舊 random 對應的新節點 / copy's random
        }

        return map[head];  // 回傳頭節點的副本；head 為 null 時 map[head] 也是 nullptr / head's copy
    }
};

複雜度 / Complexity

• Time: O(n) — 兩種做法都只把串列走固定次數（交錯法 3 趟、雜湊表法 2 趟），每個節點做常數工作。n 是節點數。Each approach makes a constant number of passes over the list, doing O(1) work per node; n is the number of nodes.
• Space:
• 原地交錯 C 版：O(1) 額外空間——除了必須配置的 n 個新節點（這是輸出，不計入），沒有用到額外資料結構。Only the required n output nodes; no auxiliary structure.
• 雜湊表 C++ 版：O(n) 額外空間——unordered_map 存了 n 組「舊 → 新」對應。The map holds n old→new entries.

Pitfalls & Edge Cases

• 空串列 / Empty list (head == null)： C 版一開始就 return NULL；C++ 版靠 map[nullptr] == nullptr 自然回傳 nullptr。不特別處理就會對空指標解參考而崩潰。Dereferencing a null head would crash.
• random 為 null / null random： 交錯法第二趟一定要先檢查 cur->random != NULL，否則 cur->random->next 會對 null 解參考。C++ 版靠 map[nullptr] 自動給 nullptr，較不易出錯。
• 交錯時把「下一個」搞混 / Losing the next pointer： Pass 1 必須先用 copy->next = cur->next 記住原本的下一個，再改 cur->next = copy；順序反了就會遺失後半段串列。Save the old next before overwriting it.
• 沒把舊串列還原 / Not restoring the original： 面試官通常要求舊串列保持不變。交錯法的 Pass 3 就是為了把 A → A' → B 還原成 A → B，別漏掉。
• random 指向自己或前面的節點 / random pointing backward or to self： 這完全合法，兩種做法都能正確處理，因為所有新節點在接指標前就已全部建好（或整條交錯結構已就緒）。All copies exist before any pointer is wired, so any target resolves correctly.
• 回傳錯的頭 / Returning the wrong head： 交錯法要回傳 head->next（第一個副本），不是 head；務必在 Pass 3 拆開前先存好 newHead，因為拆開後 head->next 會變回舊串列。