LeetCode 138中等链表
复制带随机指针的链表 图解题解
链表有额外随机指针，深拷贝怎么不出错？两遍遍历各司其职。
复制带随机指针的链表，就像替一群互相认识的人做身份证副本：第一遍只给每个人拍照新证（建 map，旧节点→新节点），但还不填「认识谁」那栏；第二遍再走一遍，用 map 把每张新证的 next 和 random 对应填好——两遍分工，第一遍建映射、第二遍接线，缺哪遍都乱套。
这道题到底在问什么
复制一条链表，每个节点除了 next，还有 random 指向任意节点。
- 示例
- [[7,null],[13,0],[11,4]] → 深拷贝新链表
最优解：一步一步想明白
- 3只复制 next 会漏掉 random；先连 random 又找不到新节点。
- 4第一遍给每个旧节点创建新节点并记映射，第二遍补 next 和 random。
- 5map = {}每个节点除了 next，还有一根 random 随机指针。深拷贝要把 next 和 random 都复制对，难点在 random 可能指向还没创建的节点。
- 6map[7] = 7′第一遍只做一件事：cur 走到 7，新建一个值为 7 的拷贝 7′，在 map 里记下 7→7′。先不接任何箭头。
- 7map 满 · 4 项cur 一路走到底，每个原节点都映射出一个孤立的拷贝（只有值、还没箭头）。map 现在能用原节点查到对应拷贝——这是第二遍接线的关键。
- 87′.next = map[13] = 13′第二遍 cur 重新从头走：拷贝的 next 用 map 接——原 7 的 next 是 13，所以 7′.next = map[13] = 13′。一路把拷贝链的 next 全接好。
- 913′.random = map[7] = 7′random 同理：原 13 的 random 指向 7，于是 13′.random = map[7] = 7′。next 和 random 都用 map 翻译完，深拷贝完成，返回 map[head]=7′。
- 12一句话记住：第一遍给每个旧节点创建新节点并记映射，第二遍补 next 和 random。
- 15map[13] 还不存在 → 取到 null雷区：若想第一遍就接 7′.next = map[13]，但此刻 13′ 还没建，map[13] 是空的→接到 null。所以必须先全建完（第一遍）、再统一接线（第二遍）。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=linkedlist 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：只照着眼前元素做局部判断
✓ 对：维护动画里的完整状态
本题的答案由状态转移决定，少一个状态就会漏情况。
✗ 错：边界输入不单独跑
✓ 对：先跑空/单元素/重复/极端值
这些输入最容易暴露初始化和越界问题。
完整代码（Python / C++ / Java）
Python
class Solution:
def copyRandomList(self, head):
old_to_new = {None: None}
cur = head
while cur:
old_to_new[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur:
old_to_new[cur].next = old_to_new[cur.next]
old_to_new[cur].random = old_to_new[cur.random]
cur = cur.next
return old_to_new[head]C++
class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*, Node*> mp;
mp[nullptr] = nullptr;
for (Node* cur = head; cur; cur = cur->next) {
mp[cur] = new Node(cur->val);
}
for (Node* cur = head; cur; cur = cur->next) {
mp[cur]->next = mp[cur->next];
mp[cur]->random = mp[cur->random];
}
return mp[head];
}
};Java
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> mp = new HashMap<>();
mp.put(null, null);
for (Node cur = head; cur != null; cur = cur.next) {
mp.put(cur, new Node(cur.val));
}
for (Node cur = head; cur != null; cur = cur.next) {
mp.get(cur).next = mp.get(cur.next);
mp.get(cur).random = mp.get(cur.random);
}
return mp.get(head);
}
}套路模板 · 复制带随机指针的链表迁移骨架
# 1. 定义状态
state = init()
# 2. 按顺序读输入
for x in data:
update(state, x) # 只做本题允许的安全转移
# 3. 从状态里取答案
return answer(state)// 1. init state
for (auto x : data) {
// update state with the same invariant
}
return ans;// 1. init state
for (int x : data) {
// update state with the same invariant
}
return ans;复杂度
时间复杂度
O(n)
每个状态只按核心结构推进有限次
空间复杂度
O(n)
保存状态、栈/堆/表/访问集合
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 复制带随机指针的链表 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心状态是什么？+
第一遍给每个旧节点创建新节点并记映射，第二遍补 next 和 random。
这道题为什么用「链表」，换最直接的暴力解会差在哪？+
链表抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。