如何复制带随机指针的链表？

简化版

带随机指针链表需要深拷贝每个节点，并正确复制 next 和 random。常见做法有两种：哈希表记录“原节点 -> 新节点”的映射，或把新节点插到原节点后面，再拆分链表；前者清晰，后者额外空间 O(1)。

详细版

哈希表法分两遍：第一遍为每个原节点创建新节点并放入 map；第二遍根据 map 设置新节点的 next 和 random。

map[old] = copy
copy.next = map[old.next]
copy.random = map[old.random]

原地穿插法分三步：复制节点插到原节点后面；利用 old.random.next 设置新节点 random；最后把原链表和复制链表拆开。面试要强调这是深拷贝，不能让新链表节点指向旧链表节点。

完整版教学

一、难点在 random 可能指向任意节点

普通链表复制只需要顺着 next 走，边遍历边创建新节点即可。带 random 指针时，每个节点还可能指向链表中任意节点或 null。

A -> B -> C
A.random -> C
B.random -> A
C.random -> null

复制后，新 A 的 random 应该指向新 C，而不是旧 C。这就是深拷贝的核心。

记忆钩子：复制 random 时要找“旧指针对应的新节点”。

二、哈希表法最直观

第一遍遍历原链表，为每个旧节点创建一个新节点，建立映射。

Map<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) {
  map.put(cur, new Node(cur.val));
  cur = cur.next;
}

第二遍再补指针：

cur = head;
while (cur != null) {
  Node copy = map.get(cur);
  copy.next = map.get(cur.next);
  copy.random = map.get(cur.random);
  cur = cur.next;
}
return map.get(head);

map.get(null) 在很多语言里要自己处理，Java HashMap 可以返回 null。

三、为什么不能一遍简单复制

如果 A.random 指向 C，而遍历到 A 时 C 的新节点还没创建，就没法设置 A’ 的 random。

current A
A.random -> C
C copy not created yet

当然可以先留空以后补，但这本质还是需要某种“旧节点到新节点”的映射。哈希表就是最直接的映射结构。

时间 O(n)，空间 O(n)，面试可读性最好。

四、穿插法把映射藏在链表里

穿插法第一步：每个旧节点后面插入复制节点。

A -> B -> C

A -> A' -> B -> B' -> C -> C'

此时旧节点 A 的复制节点就是 A.next。这相当于不用哈希表也能找到“旧 -> 新”的映射。

代码思路：

Node cur = head;
while (cur != null) {
  Node copy = new Node(cur.val);
  copy.next = cur.next;
  cur.next = copy;
  cur = copy.next;
}

五、设置 random 和拆分链表

设置 random 时，如果 cur.random 不为空，那么 cur 的复制节点是 cur.next，cur.random 的复制节点是 cur.random.next。

cur.next.random = (cur.random == null) ? null : cur.random.next;

最后拆分：

A -> A' -> B -> B' -> C -> C'

old:  A -> B -> C
copy: A' -> B' -> C'

拆分时既要恢复原链表，也要连好新链表。这个步骤是穿插法最容易断指针的地方。

六、两种方法怎么选

方法	时间	额外空间	优点	风险
哈希表	O(n)	O(n)	清晰，不改原链表结构	需要额外内存
穿插法	O(n)	O(1)	空间省	临时修改原链表，指针更绕

如果面试要求先写正确，哈希表法更稳。如果追问空间优化，再讲穿插法。

真实工程里如果原链表正在被其他线程读，穿插法临时改结构可能不安全。

七、常见误区与追问

误区：复制 random 时可以直接指向旧节点。 深拷贝要求新链表内部自洽，不能指向旧链表节点。
误区：只复制 next 就完成了。 random 是题目核心，必须复制到对应的新节点。
误区：穿插法完全没有副作用。 它会临时改变原链表结构，不适合并发读场景。
追问：哈希表法为什么要两遍？ 第一遍建立所有旧到新的映射，第二遍才能安全设置任意 random。
追问：穿插法为什么空间 O(1)？ 映射关系由 old.next 隐式表示，不需要额外 map。
追问：空 random 怎么处理？ 新节点 random 也应为 null，不能访问 cur.random.next。

八、加强记忆

复制随机链表记成“先建映射，再补指针”。哈希表法把旧节点到新节点的关系放进 map，最清楚；穿插法把复制节点插在旧节点后面，用 old.next 隐式表示映射，空间更省。无论哪种方法，核心都不能变：新链表的 next 和 random 必须指向新节点，不能偷指旧节点。

简化版

详细版