Description
給定一個鏈結串列，每個節點除了
next指針外，還有一個random指針可以指向串列中任意節點或 null。回傳該串列的深拷貝。
Example:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Intuition#
核心思路：用 HashMap 建立「原節點 -> 新節點」的映射，解決 random 指針無法在第一次遍歷時確定的問題。
- 難點在於 random 指針可能指向尚未建立的節點
- HashMap 方法：先建立所有新節點的映射，再設定 next 和 random
- 進階：Interleave 方法可在 O(1) 空間內完成
Approaches#
1: HashMap (Two-Pass)#
- 概念: 第一次遍歷建立所有新節點並存入 HashMap（原節點 -> 新節點）；第二次遍歷透過 HashMap 設定 next 和 random
- 時間複雜度:
O(n)- 兩次遍歷 - 空間複雜度:
O(n)- HashMap 存放 n 個映射
class Solution {
fun copyRandomList(node: Node?): Node? {
if (node == null) return null
val map = HashMap<Node, Node>()
// 第一次遍歷：建立所有新節點
var curr = node
while (curr != null) {
map[curr] = Node(curr.`val`)
curr = curr.next
}
// 第二次遍歷：設定 next 和 random
curr = node
while (curr != null) {
map[curr]!!.next = map[curr.next]
map[curr]!!.random = map[curr.random]
curr = curr.next
}
return map[node]
}
}⭐2: Interleave (O(1) Space)#
- 概念: 三步驟：(1) 在每個原節點後插入其複製節點 (2) 利用交錯結構設定 random (3) 分離原串列和複製串列
- 時間複雜度:
O(n)- 三次遍歷 - 空間複雜度:
O(1)- 不需要額外資料結構（輸出不算）
class Solution {
fun copyRandomList(node: Node?): Node? {
if (node == null) return null
// Step 1: 在每個節點後插入複製節點 A -> A' -> B -> B'
var curr = node
while (curr != null) {
val copy = Node(curr.`val`)
copy.next = curr.next
curr.next = copy
curr = copy.next
}
// Step 2: 設定複製節點的 random
curr = node
while (curr != null) {
curr.next!!.random = curr.random?.next
curr = curr.next!!.next
}
// Step 3: 分離兩個串列
val dummy = Node(0)
var copyTail = dummy
curr = node
while (curr != null) {
val copy = curr.next!!
val next = copy.next
copyTail.next = copy
copyTail = copy
curr.next = next
curr = next
}
return dummy.next
}
}Interleave 方法在分離時必須同時還原原串列，否則會破壞原始資料結構。面試中若不確定，HashMap 方法更安全。
補充：One-Pass HashMap with getOrPut
利用 getOrPut 在一次遍歷中同時建立節點和設定指針。遇到新節點時自動建立，遇到已存在的節點則直接取用。
class Solution {
fun copyRandomList(node: Node?): Node? {
if (node == null) return null
val map = HashMap<Node, Node>()
fun getOrCreate(n: Node?): Node? {
if (n == null) return null
return map.getOrPut(n) { Node(n.`val`) }
}
var curr = node
while (curr != null) {
val copy = getOrCreate(curr)!!
copy.next = getOrCreate(curr.next)
copy.random = getOrCreate(curr.random)
curr = curr.next
}
return map[node]
}
}🔑 Takeaways#
- Pattern: 「原節點 -> 新節點」的映射是深拷貝問題的核心思路
- 關鍵技巧: Interleave 技巧（在原節點後插入複製節點）可以巧妙地利用位置關係取代 HashMap，達到 O(1) 空間