题型地图 56天全屏 141题

当前：LC138 · 随机链表的复制 · 首次出现于 Day 48 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

60 / 141回到 Day 48 卡片 141 题索引

LC138

复制带随机指针的链表 · 为什么必须先建 oldToNew 映射表

链表 · 哈希克隆 · 两遍扫描

这不是普通的链表复制。每个节点除了 next 指针,还多一个random,可能指向链表中任意节点,也可能是 nil。难点在于:复制时 random 指向的可能是 *还没被复制* 的节点 —— 我们必须先把 “翻译表” 建出来。

当前样例

LeetCode 官方示例 · 5 节点

输入 [[7,null],[13,0],[11,4],[10,2],[1,0]]

5 个节点 7 → 13 → 11 → 10 → 1;random 指向: 13→7, 11→1, 10→11, 1→7;节点 7 的 random 为 nil。

random 既可以指向链表中任意节点,也可以是 nil — 这就是为什么要用 map 记账。

n = 5

输出

深拷贝链表 head

新链表结构、值、next/random 都与原链表一致,但全部是新对象

时间复杂度O(n)

两遍扫描链表,每个节点常数次操作

空间复杂度O(n)

oldToNew 哈希表存 n 个键值对

题意直觉 · 这不是复制值,是复制一整张引用关系图

普通链表复制只需要顺着 next 一路 new 节点。但这题每个节点还有 random,它可能跳到链表中任意位置,甚至指向自己,或者为 nil。所以复制时,我们不仅要复制节点,还要把节点之间的指针关系图原样搬过去。

LeetCode 输入格式

[[7,null],[13,0],[11,4],[10,2],[1,0]]

[7, null] · 值为 7,random 为 nil
[13, 0] · 值为 13,random 指向下标 0 的节点(也就是 7)
[11, 4] · 值为 11,random 指向下标 4 的节点(也就是 1)

一句核心表达

我们不是复制节点值,而是复制整张引用关系图。
random 指向的是旧节点,所以必须先知道每个旧节点对应的新节点是谁。

一旦把 “旧 → 新” 映射建好,所有指针都可以通过这张表翻译,新链表就和旧链表彻底解耦。

测试样例 · 切换后整段动画会重算

反例 · 为什么不能 newNode.random = oldNode.random

很多人第一反应是边遍历边复制:new 一个节点,把 next 和 random “顺手抄过去”。看起来很自然 ——

// ✗ 错误做法
for cur := head; cur != nil; cur = cur.Next {
    newNode := &Node{Val: cur.Val}
    newNode.Next = cur.Next       // ✗ 指向旧节点
    newNode.Random = cur.Random   // ✗ 指向旧节点
}

Bug ① 新链表的指针指向旧节点

cur.Random 是旧节点的指针,直接赋给 newNode.Random,意味着新链表的 random 还是指向旧链表 —— 新旧链表没有真正分离。

Bug ② random 可能指向未来

random 可以指向链表中任意节点,包括还没遍历到的后面。一遍扫描时你根本不知道 “新版的那个节点” 是谁,只能拿到旧节点的引用。

启示

复制不是复制值,是复制 引用关系图。要让指针指向新节点,必须先有一张 oldToNew 翻译表。建表之后,任何 “指向旧节点的指针” 都能一查变成 “指向新节点的指针”。

正确思路 · oldToNew “引用翻译表”

把 oldToNew 看作一张翻译表:

oldToNew[旧节点 A] = 新节点 A'

// 以后看到任何指针指向旧节点 A,
// 都统一改写成指向新节点 A'

第一遍 · 只创建新节点

沿原链表走一遍,为每个旧节点 new 一个对应的新节点,放入 map。不连 next,不连 random —— 因为它们可能还没出现。

第二遍 · 通过 map 翻译指针

再走一遍原链表。对每个旧节点 cur,让 copy = oldToNew[cur],然后 copy.Next = oldToNew[cur.Next]、 copy.Random = oldToNew[cur.Random]。

Go 小细节

Go 中 oldToNew[nil] 返回零值 nil,所以 cur.Next 或 cur.Random 为 nil 时,不需要额外的 if 判断 — 代码可以非常干净。

题意题目 · 复制带 random 指针的链表Step 1/24

三层舞台 · 上(旧链)· 中(oldToNew)· 下(新链)

[[7,null],[13,0],[11,4],[10,2],[1,0]]

旧链表 · 只读 · random 用灰色箭头

中层 · oldToNew · 引用翻译表

0 / 5 条

oldToNew = ∅ · 第一遍尚未开始

新链表 · random 用蓝色箭头

旧链 random新链 randomnext(新链)当前聚焦映射表 = 旧节点 → 新节点

当前发生了什么

题目 · 复制带 random 指针的链表

给你一条链表 7 → 13 → 11 → 10 → 1。除了 next,每个节点还有一个 random 指针,可能指向链表中任意节点,也可能是 nil。要求返回这条链表的深拷贝 —— 新链表的每个节点都是新对象,但结构、值、next/random 关系与原链表完全一致。

为什么这一步是对的

这题考的不是复制节点值,而是复制对象之间的引用关系。random 指向的是旧节点,所以必须先知道每个旧节点对应的新节点是谁。

不变量 · 尚未创建任何 clone;oldToNew 为空。

面试该怎么说 · 复述需求:深拷贝 + random 指针。强调难点:random 可能指向后面的节点甚至 nil,所以不能边走边复制。

代码同步 · Go

题意

1func copyRandomList(head *Node) *Node {
2    if head == nil {
3        return nil
4    }
5 
6    oldToNew := map[*Node]*Node{}
7 
8    // 第一遍:只创建新节点
9    for cur := head; cur != nil; cur = cur.Next {
10        oldToNew[cur] = &Node{Val: cur.Val}
11    }
12 
13    // 第二遍:连接 next 和 random
14    for cur := head; cur != nil; cur = cur.Next {
15        copy := oldToNew[cur]
16        copy.Next = oldToNew[cur.Next]
17        copy.Random = oldToNew[cur.Random]
18    }
19 
20    return oldToNew[head]
21}

行 10oldToNew[cur] = &Node{Val: cur.Val} · 第一遍只做这件事:把每个旧节点登记进 map,暂不连任何指针。

行 16-17copy.Next = oldToNew[cur.Next]、copy.Random = oldToNew[cur.Random] · 通过 map 把旧节点指针翻译成新节点指针。oldToNew[nil] == nil,无需 if。

剧本时间线 · 共 24 步

为什么必须两遍扫描

一遍扫描的死结

如果你想边走边连,当处理到节点 13 时,它的 random 指向节点 7。但节点 7 的新副本呢? 你没办法回头改 — 而 random 也可能指向后面还没创建的节点,你更没办法预知。

“走到哪连到哪” 在这题根本走不通,因为 random 的目标分布是任意的。

两遍扫描的分工

第一遍 · 建表:只 new 节点 + 写入 oldToNew。不连任何指针。
第二遍 · 翻译:对每个旧节点 cur,让 copy = oldToNew[cur],然后 copy.Next = oldToNew[cur.Next]、 copy.Random = oldToNew[cur.Random]。
第二遍开始时,map 已经覆盖整条链表,所以 random 无论指哪都能查到。

正确性不变量

①每个旧节点只对应一个新节点 · len(oldToNew) == n。
②新链表中的 next / random都必须指向新节点或 nil,绝不能指向旧节点。
③oldToNew[nil] = nil · Go 中 map 对不存在 key 返回零值,因此空指针自动正确处理。

面试回答模板

这题是典型深拷贝问题。因为 random 指针可能指向链表中任意节点,甚至为 nil,所以不能直接复用旧节点的 random。

我会用哈希表 oldToNew 记录每个旧节点对应的新节点。第一遍遍历原链表,只创建新节点并放入 map。第二遍再次遍历原链表,对于每个旧节点 cur,让 copy = oldToNew[cur],然后 copy.Next = oldToNew[cur.Next], copy.Random = oldToNew[cur.Random]。

这样可以保证新链表的所有 next/random 都指向新节点,而不是旧节点。时间复杂度 O(n),空间复杂度 O(n)。

常见误区

✗ newNode.random = oldNode.random — 新链表的 random 仍然指向旧节点。
✗ 一遍扫描就想连 random — random 可能指向尚未创建的节点。
✗ 忘记处理 head == nil 直接 return nil。
✗ 对 cur.Random == nil 单独写 if — 其实 oldToNew[nil] 自然返回 nil,可省略。
✗ 把空间复杂度写成 O(1) — 没考虑 map,正确为 O(n)。

进阶 · O(1) 空间的交错复制法

另一种做法不借助 map:把每个新节点 A' 直接插在旧节点 A 后面,形成 A → A' → B → B' → …,这样 A.Next.Random = A.Random.Next, 再把奇偶链表拆开即可。空间 O(1),但代码细节多 —— 哈希表两遍法已经足够清晰、面试也可以直接交付。