复制带随机指针的链表 图解题解
链表有额外随机指针，深拷贝怎么不出错？两遍遍历各司其职。
复制带随机指针的链表，就像替一群互相认识的人做身份证副本：第一遍只给每个人拍照新证（建 map，旧节点→新节点），但还不填「认识谁」那栏；第二遍再走一遍，用 map 把每张新证的 next 和 random 对应填好——两遍分工，第一遍建映射、第二遍接线，缺哪遍都乱套。
这道题到底在问什么
- 输入
- 7 → 13 → 11 → 10（random：13→7, 11→10, 10→13, 7→null）
- 输出
- 同构副本链表
最优解：一步一步想明白
- 3记住这一招：先复制全部、再用 map 取副本连线。
- 4这是原链表：上方一排是原节点，灰线是它的 next 与 random 指针。右侧 map 现在还是空的，我们要逐个建出副本。
- 5阶段①复制：来到节点 7，新建一个值相同的副本 7'（此时副本的 next/random 都先留空），准备写入 map。
- 6写入 map[7] = 7'。副本已登记，右侧 map 多了一条「7 → 7'」。
- 7阶段①复制：来到节点 13，新建一个值相同的副本 13'（此时副本的 next/random 都先留空），准备写入 map。
- 8写入 map[13] = 13'。副本已登记，右侧 map 多了一条「13 → 13'」。
- 9阶段①复制：来到节点 11，新建一个值相同的副本 11'（此时副本的 next/random 都先留空），准备写入 map。
- 10写入 map[11] = 11'。副本已登记，右侧 map 多了一条「11 → 11'」。
- 11阶段①复制：来到节点 10，新建一个值相同的副本 10'（此时副本的 next/random 都先留空），准备写入 map。
- 12写入 map[10] = 10'。副本已登记，右侧 map 多了一条「10 → 10'」。
- 13阶段②连 next：看原图，7 的 next 指向 13（高亮这条边）。
- 14用 map 取副本：7'.next = map[13] = 13'。副本之间的 next 接上了。
- 15阶段②连 next：看原图，13 的 next 指向 11（高亮这条边）。
- 16用 map 取副本：13'.next = map[11] = 11'。副本之间的 next 接上了。
- 17阶段②连 next：看原图，11 的 next 指向 10（高亮这条边）。
- 18用 map 取副本：11'.next = map[10] = 10'。副本之间的 next 接上了。
- 19阶段②连 next：节点 10 是尾节点，原 next 为 null，于是副本 10'.next 也置 null。next 链全部连完。
- 20阶段③连 random：节点 7 的 random 为 null，副本 7'.random 也置 null。
- 21阶段③连 random：原图里 13 的 random 指向 7（高亮这条 random 边）。
- 22用 map 取副本：13'.random = map[7] = 7'。哪怕 random 指向链表中间，也能精准接上——这正是先建 map 的好处。
- 23阶段③连 random：原图里 11 的 random 指向 7（高亮这条 random 边）。
- 24用 map 取副本：11'.random = map[7] = 7'。哪怕 random 指向链表中间，也能精准接上——这正是先建 map 的好处。
- 25阶段③连 random：原图里 10 的 random 指向 13（高亮这条 random 边）。
- 26用 map 取副本：10'.random = map[13] = 13'。哪怕 random 指向链表中间，也能精准接上——这正是先建 map 的好处。
- 27全部节点都已复制、next 与 random 都按原图连上了。返回 map[头节点] = 7' 这个副本头，就是整条链表的深拷贝。
⚠️ 容易写错的地方
✗ 错：边复制边连 random
✓ 对：先把所有副本都建出来写进 map，再统一连指针
random 可能指向后面还没建出的节点，先建全才取得到
✗ 错：random 连到原节点
✓ 对：连的是 map[原.random] 这个副本，不是原节点本体
连错就成了对原链表的引用，不是深拷贝
✗ 错：忘了处理 random=null
✓ 对：map.get(null) 自然返回 null，副本.random 置 null
尾部/无 random 的节点要正确收尾
完整代码（Python / C++ / Java）
Python
def copyRandomList(head):
if not head: return None
mp = {} # 原节点 -> 克隆副本
cur = head
while cur: # 阶段1：先复制每个节点
mp[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur: # 阶段2+3：按原图连 next 和 random
mp[cur].next = mp.get(cur.next)
mp[cur].random = mp.get(cur.random)
cur = cur.next
return mp[head]C++
Node* copyRandomList(Node* head){
if(!head) return nullptr;
unordered_map<Node*,Node*> mp;
for(Node* c=head; c; c=c->next) // 阶段1：复制节点
mp[c] = new Node(c->val);
for(Node* c=head; c; c=c->next){ // 阶段2+3：连指针
mp[c]->next = mp[c->next];
mp[c]->random = mp[c->random];
}
return mp[head];
}Java
public Node copyRandomList(Node head) {
if (head == null) return null;
Map<Node, Node> mp = new HashMap<>();
for (Node c = head; c != null; c = c.next) // 阶段1：复制节点
mp.put(c, new Node(c.val));
for (Node c = head; c != null; c = c.next) { // 阶段2+3：连指针
mp.get(c).next = mp.get(c.next);
mp.get(c).random = mp.get(c.random);
}
return mp.get(head);
}复杂度
时间
O(N)
两遍线性遍历：复制一遍、连指针一遍
空间
O(N)
哈希表存 N 个「原 → 副本」映射
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 复制带随机指针的链表 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不用哈希表、做到 O(1) 额外空间？+
能。经典「原地交织」法：把每个副本插在原节点后面（A→A'→B→B'…），借位置关系设 random（cur.next.random = cur.random.next），最后拆分两条链。省了 map，但步骤更绕。
哈希表的 key 用什么？+
用「原节点的引用/地址」作 key、克隆副本作 value。这样 next 和 random 指到哪个原节点，都能 O(1) 取到它对应的副本。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 复制带随机指针的链表 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。