題目描述:給定一個鏈結串列,其中每個節點包含一個整數值 val、一個指向下一個節點的指標 next,以及一個可以指向串列中任意節點(或 nullptr)的隨機指標 random。請對此串列進行深度複製(deep copy),返回新串列的頭節點。新串列中的每個節點都必須是全新建立的,不能與原串列共用任何節點。
解題思路:此題的難點在於 random 指標可以指向串列中的任意位置。在複製時,若我們尚未建立後面的節點,就無法立即設定 random 指標的指向,因此需要一個兩步驟或特殊的策略。
方法一:哈希表(最直觀)
使用一個哈希表(unordered_map)儲存原節點到新節點的映射關係。分兩遍走訪:
next 和 random 指標。方法二:交織節點法(O(1) 空間,最優解)
不使用額外的哈希表,而是透過修改原串列結構來記錄映射關係,分三個階段:
A → A' → B → B' → ... 的結構。A',其 random 應指向 A.random.next(即原節點的 random 指向的節點的下一個,也就是複製節點)。哈希表方法更易理解,是面試中最常見的解法;交織節點法則展示了 O(1) 空間的可能性。
時間複雜度: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):以遞迴方式走訪串列,用哈希表記錄已建立的節點以避免重複建立。此方法邏輯簡潔,但在串列較長時會有堆疊溢位的風險,且效能與迭代版本相同,通常不作為首選解法。
prev、next、random 三個指標),你的解法需要做哪些調整?