解題說明
Copy List with Random Pointer
題目描述：給定一個鏈結串列，其中每個節點包含一個整數值 val、一個指向下一個節點的指標 next，以及一個可以指向串列中任意節點（或 nullptr）的隨機指標 random。請對此串列進行深度複製（deep copy），返回新串列的頭節點。新串列中的每個節點都必須是全新建立的，不能與原串列共用任何節點。
解題思路：此題的難點在於 random 指標可以指向串列中的任意位置。在複製時，若我們尚未建立後面的節點，就無法立即設定 random 指標的指向，因此需要一個兩步驟或特殊的策略。
方法一：哈希表（最直觀）
使用一個哈希表（unordered_map）儲存原節點到新節點的映射關係。分兩遍走訪：
- 第一遍：為每個原節點建立對應的新節點，存入哈希表。
- 第二遍：走訪原串列，利用哈希表找到對應的新節點，設定其
next和random指標。
方法二：交織節點法（O(1) 空間，最優解）
不使用額外的哈希表，而是透過修改原串列結構來記錄映射關係，分三個階段：
- 交織：在原串列的每個節點後方插入其複製節點，形成
A → A' → B → B' → ...的結構。 - 設定 random：對於每個新節點
A'，其random應指向A.random.next（即原節點的 random 指向的節點的下一個，也就是複製節點）。 - 分離：將交織的串列拆分回兩個獨立的串列，恢復原串列並取出複製串列。
哈希表方法更易理解，是面試中最常見的解法；交織節點法則展示了 O(1) 空間的可能性。
C++ 解法
複雜度分析
時間複雜度：O(n) — 我們對原串列進行了兩次完整的線性走訪：第一次建立所有複製節點並存入哈希表，第二次設定每個複製節點的 next 和 random 指標。每次走訪均為 O(n)，總時間複雜度為 O(n)。
空間複雜度：O(n) — 哈希表儲存了 n 個原節點到複製節點的映射，需要 O(n) 的額外空間。若使用交織節點法，則可將額外空間降至 O(1)（不計算輸出所需的空間），但實作複雜度相對較高。
虛擬碼
1. If head is null, return null. 2. First pass — create copies: a. Walk through each node in the original list. b. For each node, create a new Node with the same val and store the mapping: nodeMap[original] = copy. 3. Second pass — wire pointers: a. Walk through each node in the original list again. b. Set nodeMap[curr]->next = nodeMap[curr->next] (if curr->next is not null). c. Set nodeMap[curr]->random = nodeMap[curr->random] (if curr->random is not null). 4. Return nodeMap[head] as the head of the deep-copied list.
其他解法
交織節點法 O(n) 時間 / O(1) 空間：不使用哈希表，而是將複製節點直接插入原串列中（每個原節點後插入其複本），形成交錯排列。接著利用「複製節點的 random = 原節點的 random 的 next 節點」這一規律設定所有 random 指標，最後再將兩條串列分離。此方法節省了哈希表的空間，但會暫時修改原串列結構，需要謹慎處理指標操作，且三個階段的代碼較為冗長。
遞迴 + 哈希表 O(n)：以遞迴方式走訪串列，用哈希表記錄已建立的節點以避免重複建立。此方法邏輯簡潔，但在串列較長時會有堆疊溢位的風險，且效能與迭代版本相同，通常不作為首選解法。
延伸思考
- 如果要在 O(1) 額外空間（不計算輸出）內完成深度複製，你會如何實作交織節點法？請描述三個步驟並分析其中最容易出錯的地方。
- 若此題的節點結構改為雙向鏈結串列（每個節點有
prev、next、random三個指標），你的解法需要做哪些調整？ - 此題的「深度複製」概念在軟體工程中有廣泛應用。請舉出除鏈結串列外，至少兩種需要深度複製而非淺層複製的資料結構或場景，並說明為何淺層複製會造成問題。