題目與適用情境
給定一條無環單向鏈結串列的頭節點。每個節點包含 val、next 與 random；random 可以是 null，也可以指向透過 next 可達的任意節點，包括目前節點本身。請回傳一份深拷貝：每個原節點恰好對應一個新節點。如果原節點 x 的某個指標指向原節點 y，那麼 x 的副本也必須透過同一欄位指向 y 的副本。
節點值可以重複，因此值不能代表節點身分。next 鏈有限且無環，但 random 可以向前、向後指，也可以形成環。回傳結果不能與輸入共享節點；函式回傳時，輸入鏈結串列也必須保持原有結構。
這題考資料結構與物件身分。基礎解法用映射表記錄「原節點到副本節點」；若追問要求常數輔助空間，可以暫時把副本插在原節點後面，完成指標設定後再還原輸入。必要的輸出節點不算輔助空間，但總記憶體仍包含 O(n) 個新節點。
面試官評估重點
第一個訊號是能否從結構上定義深拷貝。值相等還不夠，必須存在從原節點到新節點的一對一映射 f，並同時保持兩類關係：x.next 的副本是 f(x).next，x.random 的副本是 f(x).random。
第二個訊號是如何處理「參照目標還沒被複製」的情況。只沿著串列走一遍並複製值，無法安全連接向前的 random。穩妥方案把配置與連線拆開：先建立所有目標節點，再透過身分映射連接指標。
第三個訊號是能否推導空間最佳化。把每個副本緊接在原節點之後，就建立了局部不變量：任一原節點 r 的副本恰好是 r.next。設定隨機指標時，這個拓撲關係可以取代映射表。
最後要看輸入還原是否完整。交錯法只有在還原每個原節點的 next、抽出正確的副本鏈，並說明何時不能暫時修改輸入後，才算完整答案。
回答前需要釐清的問題
random能否指向串列外？ 本題不能。如果外部節點也要複製，範圍會變成一般可達圖；如果不複製，題目必須說明要保留、清除或拒絕外部參照。next能否成環？ 本題不能。若可以，只沿next走且不記錄已拜訪節點會永不結束，應改成圖複製。- 能否暫時修改輸入？ 映射法完全不修改。交錯法會暫時修改，只適用於整個呼叫期間獨占可變存取，且回傳前能還原原串列的情況。
- 額外空間如何計算？ 新節點是必要輸出。映射表使用
O(n)輔助空間；交錯法除輸出外只使用O(1)個工作指標。 - 節點值唯一嗎？ 不唯一。依值建立映射會合併不同節點，必須依物件身分建立映射。
- 空輸入回傳什麼？ 回傳
null。
30 秒回答框架
「我會先用原節點到副本節點的身分映射。第一輪建立全部副本，第二輪查表設定副本的 next 與 random，時間 O(n)、輔助空間 O(n)。如果要求常數輔助空間且允許暫時修改輸入，我會把每個副本插在原節點後面。這樣任一隨機目標的副本就是目標節點的下一個節點。第三輪拆開兩條鏈並還原輸入。兩種方案都是線性時間；交錯法排除必要輸出後只用 O(1) 輔助空間。」
分步深入解答
淺拷貝會直接重用原節點參照，因此不合格。只複製值也不夠：兩個節點可能值相同，random 還可能指向尚未走到的節點。遞迴追隨 random 也不是捷徑，因為隨機邊可能成環。
最穩妥的基礎方案明確建立一對一映射。第一輪為每個原節點建立新物件；第二輪把兩條出邊都轉換到副本節點。也可以預先記錄 null 對應 null，但面試時明確判空通常更清楚。
class RandomListNode {
val: number
next: RandomListNode | null
random: RandomListNode | null
constructor(
val: number,
next: RandomListNode | null = null,
random: RandomListNode | null = null,
) {
this.val = val
this.next = next
this.random = random
}
}
function copyWithMap(head: RandomListNode | null): RandomListNode | null {
if (head === null) return null
const copies = new Map<RandomListNode, RandomListNode>()
let current: RandomListNode | null = head
while (current !== null) {
copies.set(current, new RandomListNode(current.val))
current = current.next
}
current = head
while (current !== null) {
const copy = copies.get(current)!
copy.next = current.next === null ? null : copies.get(current.next)!
copy.random = current.random === null ? null : copies.get(current.random)!
current = current.next
}
return copies.get(head)!
}第一輪結束後的不變量很直接：沿 next 走到的每個原節點，在映射中都有且只有一個不同的新節點，後續連線不會遇到尚未建立的目標。第二輪把從 x 到 y 的邊轉換成從 f(x) 到 f(y)，結構因此被保留。兩次線性走訪的時間是 O(n)，輔助空間是 O(n)。
若要移除映射表，可以把對應關係暫時編碼進鏈結串列拓撲。先把：
A -> B -> C -> null變成：
A -> A' -> B -> B' -> C -> C' -> null此時 A' 就是 A.next。若 A.random 指向 C，那麼 A'.random 應指向 A.random.next，也就是 C'。這個關係不依賴節點值，所以向前、向後、自指與多個節點指向同一目標都能處理。
function copyByInterleaving(head: RandomListNode | null): RandomListNode | null {
if (head === null) return null
let current: RandomListNode | null = head
while (current !== null) {
const copy: RandomListNode = new RandomListNode(current.val, current.next)
current.next = copy
current = copy.next
}
current = head
while (current !== null) {
const copy: RandomListNode = current.next!
copy.random = current.random === null ? null : current.random.next
current = copy.next
}
const copiedHead = head.next
current = head
while (current !== null) {
const copy: RandomListNode = current.next!
const nextOriginal: RandomListNode | null = copy.next
current.next = nextOriginal
copy.next = nextOriginal === null ? null : nextOriginal.next
current = nextOriginal
}
return copiedHead
}正確性可由三輪不變量得到。第一輪後，每個原節點後面緊接唯一副本；第二輪中，副本的每條隨機邊都指向原目標之後的副本；第三輪每次還原一條原串列邊，同時連接一條副本串列邊。迴圈結束後，原串列完全還原，從副本頭可達的所有指標都只指向副本節點。
交錯法做三次線性走訪，時間仍為 O(n)；除固定數量的工作指標外不儲存額外結構，因此輔助空間為 O(1)，但必要的 n 個輸出節點仍占 O(n)。實務上它未必更好：前兩輪期間，其他讀取者會看到被插入副本的輸入；如果分離前拋出例外，鏈結串列可能停留在交錯狀態。映射法更容易審核，也適用於不可變或共享輸入。
測試要分別驗證結構、身分與還原。至少涵蓋：空串列；單節點且 random = null；單節點自指；重複值；兩節點隨機指標交叉；向前與向後的隨機邊；多個節點指向同一目標。複製後修改副本的值，確認原串列不變；再次走訪輸入確認 next 已還原；再斷言副本的 next 與 random 都不屬於原節點集合。
高品質示範回答
「這題的關鍵是保留節點身分，而不只是複製值。值可能重複，隨機邊可能向前或成環，所以不能依值建立映射，也不能在沒有拜訪紀錄時遞迴追隨隨機指標。
我的基礎方案是用身分映射做兩輪。第一輪沿無環的 next 鏈，為每個原節點建立一個副本；第二輪把兩類指標都透過映射轉換過去。這樣一對一關係非常明確，時間線性、輔助空間線性。如果輸入不可變、會被共享讀取，或實作可審核性更重要，我會選這個方案。
如果輔助空間必須為常數且允許暫時修改，我會把副本插在每個原節點後面。這樣任一原目標的副本就是它的 next，設定隨機指標不再需要映射。最後必須拆開交替鏈：一邊逐一還原原串列，一邊連接副本串列，確保結果沒有任何指標回到輸入。
我會說明交錯、設定隨機邊、分離三步各自的不變量，並測試自指、重複值、交叉隨機邊、空輸入與複製後的獨立修改。兩種方案都是 O(n) 時間；後者是 O(1) 輔助空間，但仍需 O(n) 輸出，而且不適合並行讀取者。」
常見錯誤
- 依節點值建立映射 → 重複值會合併不同身分 → 用原節點物件作為鍵。
- 把原
random直接指定給副本 → 輸出仍指回輸入 → 把每個非空目標轉換成對應副本。 - 在一次普通前向走訪中邊建立邊直接連線 → 向前的隨機目標可能還沒建立 → 先建立全部節點，或用完整身分映射按需建立目標。
- 不記錄拜訪狀態就遞迴追隨
random→ 隨機環會造成無限遞迴或重複節點 → 本題只沿有限的next鏈走訪；一般圖則使用已拜訪映射。 - 直接稱交錯法空間為
O(1)→ 回傳值本身仍有n個新節點 → 明確說「排除必要輸出後的O(1)輔助空間」。 - 沒有判空就計算
current.random.next→ 空隨機指標會出錯 → 明確保留null。 - 只抽出副本鏈 → 原節點之間仍夾著副本 → 在同一輪分離中還原原串列並連接副本串列。
- 對共享輸入使用交錯法 → 並行讀取者會觀察到插入的節點 → 沒有獨占修改保證時使用映射法。
- 只比較節點值 → 淺拷貝也可能通過 → 驗證物件身分、邊的轉換、原串列還原與修改隔離。
追問及應對
追問一：如果輸入從頭到尾都不允許修改呢？
使用身分映射方案。它的時間是 O(n)、輔助空間是 O(n)，整個執行過程都不會碰觸原串列。依走訪索引複製到陣列同樣需要 O(n) 空間；若輸入沒有穩定索引，仍得建立身分到索引的映射。即使交錯法最後會還原，也違反「過程中不可修改」的更強約束。
追問二：如果 random 可以指向 next 鏈之外的節點呢？
先定義複製所有權。如果外部節點也要複製，輸入就是一張有 next 與 random 兩類出邊的圖，應使用 DFS 或 BFS 搭配身分映射，讓每個可達節點只建立一次。若外部節點應被共享，契約必須允許保留外部參照。交錯法無法為任意外部目標發現或定位副本。
追問三：如果 next 也可以成環呢？
普通的判空迴圈不會結束。把兩個欄位都視為圖的邊，並維護已拜訪身分映射。第一次發現節點時建立副本，再把未拜訪鄰居加入佇列。對可達圖而言，時間與空間分別為 O(V + E) 與 O(V)；在本模型中每個節點最多有兩條出邊。
追問四：怎樣證明它真的是深拷貝？
測試中同時走訪兩條 next 鏈，建立只用於斷言的原節點到副本節點映射。檢查長度和值相等、物件身分不同，並驗證每條副本邊都等於原目標映射後的節點。還要斷言所有輸出指標都不在原節點集合中。最後修改副本的值和指標，確認原串列不變；對交錯法，再逐一比較呼叫前後的原指標身分。
追問五：實際專案會選哪一種？
預設選擇兩輪映射法，因為對應關係明確，而且不會暴露暫時修改的輸入。只有輔助記憶體確實構成限制、整個呼叫期間獨占鏈結串列、失敗處理仍能保證還原時，才選交錯法。漸進空間較低，並不能消除並行安全、例外安全與維護成本。