23 KiB
tags, create time
| tags | create time | |||||
|---|---|---|---|---|---|---|
|
2026-05-17 15:00 |
32-随机链表的复制
题面
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y。那么在复制链表中对应的两个节点 x 和 y，同样有 x.random --> y。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示Node.val的整数。random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为null。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
解释：原链表有 5 个节点。
- 节点 7 的 random 指向 null
- 节点 13 的 random 指向自己（索引 0）
- 节点 11 的 random 指向自己（索引 4，即最后一个节点 1）
- 节点 10 的 random 指向节点 10（索引 2）
- 节点 1 的 random 指向节点 13（索引 1）
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
提示：
0 <= n <= 1000-10^4 <= Node.val <= 10^4Node.random为null或指向链表中的节点。
[!warning] ⚠️ 与普通链表复制的区别 普通单向链表复制只需依次创建新节点并链接 next。但这道题多了
random指针——它可能指向已经处理过、还未处理或自身之前从未遇到过的任意节点。这意味着你不能按顺序一次性搞定每个节点的所有指针。
思路
[!question] 💡 核心难点 给定原链表中的某个节点 A，我们要创建一个新节点 A'。A'.next 很容易——它就是 A.next 对应的新节点 B'。但 A'.random 指向哪里？如果 A.random 指向 F，我们需要知道 F 对应的新节点 F' 是谁。问题是：我们在遍历过程中无法通过值来定位 F'，因为不同节点可能有相同的值。
所以核心问题归结为一句话：如何在 O(1) 或 O(n) 时间内建立"旧节点 → 新节点"的映射关系？
方法一：哈希表法（直觉方案）⭐
既然问题等价于"旧节点到新节点的查找"，那最直接的想法就是——用一张哈希表存下这个映射。
[!tip] 🔑 为什么不能靠 val 来匹配？ 看示例 3：三个节点 val 都是 3，第二个节点的 random 指向第一个节点（索引 0）。如果仅靠值相等来判断，你会把 random 指向错误的副本。必须依赖引用/地址关系而非值。
整个过程分为两轮遍历：
第一轮：创建所有新节点并建映射
flowchart LR
subgraph Map["哈希表: old → new"]
M1["A(old) → A'(new)"]
M2["B(old) → B'(new)"]
M3["C(old) → C'(new)"]
M4["D(old) → D'(new)"]
M5["E(old) → E'(new)"]
end
Map --> RESULT["拿到 copyHead = A' ✅"]
style M1 fill:#bbf,stroke:#333
style M2 fill:#bbf,stroke:#333
style M3 fill:#bbf,stroke:#333
style M4 fill:#bbf,stroke:#333
style M5 fill:#bbf,stroke:#333
style RESULT fill:#d4edda,stroke:#28a
第二轮：填充 next 和 random 指针
flowchart TD
START["遍历原链表: A→B→C→D→E"] --> STEP1["cur = A\nA'.Next = Map[A.Next] = B'\nA'.Random = Map[A.Random]\n\n比如 A.Random=nil → A'.Random=nil"]
STEP1 --> STEP2["cur = B\nB'.Next = Map[B.Next] = C'\nB'.Random = Map[B.Random]\n\n比如 B.Random=A → B'.Random=Map[A]=A'"]
STEP2 --> STEP3["对每个节点重复\n利用 Map[old] 直接查 new\nO(1) 时间"]
STEP3 --> DONE["全部设置完毕 ✅\n返回 A'"]
style START fill:#ffd700,stroke:#333
style STEP1 fill:#9df,stroke:#333
style STEP2 fill:#bbf,stroke:#333
style STEP3 fill:#f9d,stroke:#333
style DONE fill:#d4edda,stroke:#28a
逐步演示（以示例 1 为例）：
原链表：
7 13 11 10 1
(idx 0) (idx 1) (idx 2) (idx 3) (idx 4)
random=null random→0 random→2 random→4 random→1
| 轮次 | cur（旧节点） | cur.Next | cur.Random | map[旧→新] | A'.Next | A'.Random |
|---|---|---|---|---|---|---|
| 第一轮 | A(7) | → B(13) | nil | {A→A'} | — | — |
| 第一轮 | B(13) | → C(11) | → A | {A→A', B→B'} | — | — |
| 第一轮 | C(11) | → D(10) | → E | {A→A', B→B', C→C'} | — | — |
| 第一轮 | D(10) | → E(1) | → C | {A→A', B→B', C→C', D→D'} | — | — |
| 第一轮 | E(1) | nil | → B | {全5个} | — | — |
| 第二轮 | A | B | nil | — | B' | nil |
| 第二轮 | B | C | A | — | C' | A' |
| 第二轮 | C | D | A | — | D' | A' |
| 第二轮 | D | E | C | — | E' | C' |
| 第二轮 | E | nil | B | — | nil | B' |
最终结果：
7' 13' 11' 10' 1'
random=null random→A' random→A' random→C' random→B'
[!info] 🧠 映射的建立时机很关键 我们是在第一遍创建节点时就同步建好映射，这样第二遍遍历中无论 random 指向哪个旧节点，都能在 O(1) 时间内找到对应的新节点。这个设计决定了整个算法的简洁性。
时间复杂度：O(n) — 两次线性遍历
空间复杂度：O(n) — 哈希表存储 n 个映射
[!note] 🤔 Go 中使用 make(map[*Node]*Node) 还是 map[int][]*Node？ 答案是 **map[Node]Node——直接用指针地址做 key！因为只有同一个节点才能正确映射到它的副本。靠 val 不行（值可重复），靠 index 更麻烦（需要先用数组装一遍节点再编索引）。Go 的 map 天然支持指针类型的比较（比较的是内存地址），这正是我们需要的行为。
方法二：原地交织法（O(1) 空间）⭐（最优）⭐
[!question] 💡 能不能不借助额外的哈希表？ 如果我们能让新节点紧挨着旧节点出现，那么每个新节点都能通过旧节点的 next 指针"顺手"访问到下一个旧节点。更重要的是：random 的关系也能通过地址偏移自然表达——这避免了任何额外的数据结构。
这个方法的核心思想：把新节点"插"进原链表中，让它成为旧节点的后继。这样新旧节点成对交错排列，random 映射可以通过地址关系直接推导出来。
三步走策略
flowchart LR
S1["① 交织: 在每个旧节点后插入对应的副本\nA→B→C ⇒ A→A'→B→B'→C→C'"] --> S2["② 连random: 利用A'就在A后面的关系\nA'.Random = A.Random.Next\n(若A.Random存在, 则它的副本一定在它后面)"] --> S3["③ 拆分: 将新旧链表重新分离\nA→B→C 和 A'→B'→C'"]
style S1 fill:#bbf,stroke:#333
style S2 fill:#f9d,stroke:#333
style S3 fill:#d4edda,stroke:#28a
第一步：交织 —— 在新建节点的同时把它接在原节点后面
对于原链表中的每个节点 A，创建 A'，然后将 A' 插入到 A 和 A.next 之间。
// 伪代码
cur := head
for cur != nil {
nextTemp := cur.Next // 暂存 A.Next = B
cur.Next = &Node{Val: cur.Val} // 创建 A', A→A'
cur.Next.Next = nextTemp // A'→B，恢复连接
cur = nextTemp // 走到 B
}
图解（A→B→C→D 变为 A→A'→B→B'→C→C'→D→D'）：
flowchart LR
subgraph BEFORE["原始链表"]
B1["A"] --> B2["B"]
B2 --> B3["C"]
B3 --> B4["D"]
B4 -.-> END1["nil"]
end
subgraph AFTER["交织后的链表"]
A1["A"] --> AP["A']"]
AP --> B5["B"]
B5 --> BP["B']"]
BP --> C1["C"]
C1 --> CP["C']"]
CP --> D1["D"]
D1 -.-> DP["D']"]
DP -.-> END2["nil"]
end
BEFORE ==> AFTER
style AP fill:#f9d,stroke:#333
style BP fill:#f9d,stroke:#333
style CP fill:#f9d,stroke:#333
style DP fill:#f9d,stroke:#333
[!info] 🧠 这一步的精妙之处 交织完成后，每个新节点都在其对应旧节点的后面一位。这意味着如果旧节点 X 的 random 指向 Y，那么新节点 X' 的 random 就指向 Y'——而 Y' 恰好就在 Y 的后面！所以：
cur.Next.Random = cur.Random.Next（前提是 cur.Random 不为 nil）
第二步：连接 random 指针
由于新节点紧贴在旧节点后面，我们可以同时遍历旧节点和新节点，利用地址相邻的关系：
cur.Next.Random = (cur.Random == nil) ? nil : cur.Random.Next
这里的逻辑：
- 如果 cur.Random == nil → cur'.Random = nil（没有指向）
- 如果 cur.Random != nil → cur'.Random = cur.Random.Next（cur.Random 的副本恰好在它后面）
图解：
flowchart TD
A["A"] --> AR["A.Random = C"]
AR --> C["C"]
C .-> NEXT["C.Next = C'"]
A .-> AP["A']"]
AP --> NPR["A'.Random = A.Random.Next = C.Next = C'"]
AP -.随机指针已连.-> RESULT["✅ A'.Random 指向 C' 无需查找"]
style AP fill:#f9d,stroke:#333
style C fill:#bbf,stroke:#333
style RESULT fill:#d4edda,stroke:#28a
第三步：拆分成两条独立的链表
最后一步是把交织后的长链重新拆成两条：一条旧链表（保持原样）、一条新链表（完全独立）。
关键细节： 在断开 A→A' 时不能丢了 A' 后续的连接，所以需要分别维护两条链的尾指针。
// 伪代码
oldCur := head // 沿着旧链表走
newCur := head.Next // 沿着新链表走
newHead := head.Next // 保存新链表的头
for oldCur != nil {
oldCur.Next = oldCur.Next.Next // A→B，跳过 A'
if newCur.Next != nil {
newCur.Next = newCur.Next.Next // A'→B'，跳过 B
}
oldCur = oldCur.Next // 前进到下一个旧节点
newCur = newCur.Next // 前进到下一个新节点
}
return newHead
逐步拆解（A→A'→B→B'→C→C' 拆开）：
flowchart TD
SUB1["初始: A→A'→B→B'→C→C'"] --> STEP1["断开 A→A': A→B\nA'.Next 仍指 B，先不动\noldCur=B, newCur=B'"]
STEP1 --> STEP2["断开 B→B': B→C\nB'→C'\noldCur=C, newCur=C'"]
STEP2 --> STEP3["断开 C→C': C→nil\nC'→nil\n完成 ✅"]
STEP3 --> OLD["旧链表: A→B→C"]
STEP3 --> NEW["新链表: A'→B'→C'"]
style SUB1 fill:#ffd700,stroke:#333
style STEP1 fill:#9df,stroke:#333
style STEP2 fill:#bbf,stroke:#333
style STEP3 fill:#f9d,stroke:#333
style OLD fill:#eee,stroke:#999
style NEW fill:#d4edda,stroke:#28a
[!warning] ⚠️ 常见错误：newCur.Next.Next 可能越界 当新链表的末尾节点（如 D'）尝试访问 D'.Next.Next 时会 panic（nil 指针）。所以需要在访问前检查
if newCur.Next != nil。
[!note] 🤔 为什么要保留旧链表？ 题目要求返回的是新的链表，不要求恢复旧链表。但从好的工程实践来说，不修改原数据是一个好习惯。即使 LeetCode 不强制恢复，保留这个操作可以让你的代码更具普适性。
时间复杂度：O(n) — 三次线性遍历（交织、连 random、拆分），总计约 3n 步
空间复杂度：O(1) — 只用了几条临时指针变量，没有额外数据结构
代码提示
方法一：哈希表法伪代码
func copyRandomList(head):
if head == nil: return nil
// 辅助函数：根据旧节点获取（或创建）对应新节点
func getNode(map, cur):
if cur == nil: return nil
if cur not in map:
map[cur] = &Node{Val: cur.Val}
return map[cur]
cur := head
while cur != nil:
getNode(map, cur) // 确保当前节点有新节点
getNode(map, cur.Next) // 确保 next 指向的节点有新节点
getNode(map, cur.Random) // 确保 random 指向的节点有新节点
// 连指针
map[cur].Next = map[cur.Next]
map[cur].Random = map[cur.Random]
cur = cur.Next
return map[head]
方法二：原地交织法伪代码
func copyRandomList(head):
if head == nil: return nil
// 步骤 1：交织 — 在每个旧节点后插入副本
cur := head
while cur != nil:
nextTemp := cur.Next
newNode := &Node{Val: cur.Val}
cur.Next = newNode
newNode.Next = nextTemp
cur = nextTemp
// 步骤 2：连 random 指针
cur := head
while cur != nil:
if cur.Random != nil:
cur.Next.Random = cur.Random.Next
cur = cur.Next.Next // 每次跳两步，沿旧链表走
// 步骤 3：拆分成两条链表
oldCur := head
newCur := head.Next
newHead := newCur
while oldCur != nil:
oldCur.Next = oldCur.Next.Next
if newCur.Next != nil:
newCur.Next = newCur.Next.Next
oldCur = oldCur.Next
newCur = newCur.Next
return newHead
技巧
[!tip] 🔑 "先占位，后连线"模式 遇到需要建立复杂映射关系的问题，考虑是否可以先创建所有实体（节点、位置等）并建立某种结构化的组织方式，然后基于这个结构去填充关联。这本质上是"空间换时间"思想的变体——多一次遍历建结构，后续操作就简化了。
[!tip] 🔑 地址编码法（原地法的精髓） 让新元素紧跟旧元素之后排列，可以用物理位置的邻接关系替代抽象的数据结构映射。这是一种非常巧妙的"用空间布局信息代替额外存储"的技巧，类似思路还出现在「数组中去重」（用前半段存集合）、「堆排序建堆」（用树形位置关系隐含父子关系）等问题中。
[!warning] ⚠️ 常见错误 1：Go 中
&&不能与:=组合使用 这是最容易被踩的坑。下面这行代码在 C++ / Java 中可以正常工作，但在 Go 中会编译报错：// ❌ 编译错误：non-name XXX on left side of := if cur.Next != nil && _, ok := mapOldToNew[cur.Next]; !ok { ... }必须拆成两层
if，且判断必须在左侧保证非 nil。正确的写法是先检查非 nil，再在内部创建映射。
[!warning] ⚠️ 常见错误 2：只创建新节点但没有正确建立 random 映射 很多人卡在只写出了创建新节点的代码，却不知道如何高效地为 random 赋值。核心误区是试图通过遍历来找到 random 指向节点的副本——这是 O(n²) 的做法。记住要么用哈希表 O(1) 查找，要么用交织法让映射关系隐式存在于链表中。
[!warning] ⚠️ 常见错误 3：交织法拆分时漏掉边界检查 拆分阶段
newCur.Next.Next需要判断newCur.Next != nil，否则在链表末尾会 panic。这是一个非常容易遗漏的细节。
[!warning] ⚠️ 常见错误 4：混淆了"修改旧链表"和"深拷贝"的概念 深拷贝的本质是创建一组全新的对象，它们拥有与原对象相同的值和结构，但与原对象没有任何共享引用。交织法虽然暂时修改了旧链表的 next 指针，但最终会恢复原状，并且返回值是完全独立的新链表。这种"借道修改再恢复"的策略在很多算法中都有应用。
[!note] 🐹 Go 中的链表定义 LeetCode 的 Go 环境内置如下结构体定义：
type Node struct {
Val int
Next *Node
Random *Node
}
不需要手动定义，直接在解题中使用即可。
[!info] 📊 两种方法对比
| 维度 | 哈希表法（迭代） | 原地交织法 ⭐ |
|---|---|---|
| 时间复杂度 | O(n) | O(n) |
| 空间复杂度 | O(n) | O(1) |
| 代码行数 | ~25 行 | ~25 行 |
| 直观程度 | 很高（直接建映射） | 中等（需理解三趟遍历的意图） |
| 面试推荐 | ⭐⭐ 可作为铺垫讲出 | ⭐⭐⭐ 面试官期望的答案 |
| 是否修改原链表 | ❌ 完全不改 | ⚠️ 中途改了 next，最终恢复 |
[!success] ✅ 相关题目串联
- 22-相交链表 — 同样是链表上建立映射的经典场景
- 146-LRU 缓存 — 哈希表 + 双向链表的组合，也是"用哈希加速链表操作"的思路
- 24-回文链表 — 同样使用了"原地操作+反转"的模式来做到 O(1) 空间
代码
方法一：哈希表法（最直观）⭐
/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* Random *Node
* }
*/
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
// 核心思路：建立一个 hash map，key 是旧节点，value 是对应的新节点
// 这样无论 random 指向哪个节点，都能在 O(1) 时间内找到它的副本
mapOldToNew := make(map[*Node]*Node)
// ---------- 第一轮：创建所有新节点，建立 old → new 映射 ----------
cur := head
for cur != nil {
// 如果该旧节点还没有对应的副本，就创建一个
if _, ok := mapOldToNew[cur]; !ok {
mapOldToNew[cur] = &Node{Val: cur.Val}
}
// ⚠️ 注意：Go 语言中 && 不能与 := 组合使用
// 需要拆成两层 if，且判断必须在左侧保证非 nil
if cur.Next != nil {
if _, ok := mapOldToNew[cur.Next]; !ok {
mapOldToNew[cur.Next] = &Node{Val: cur.Next.Val}
}
}
if cur.Random != nil {
if _, ok := mapOldToNew[cur.Random]; !ok {
mapOldToNew[cur.Random] = &Node{Val: cur.Random.Val}
}
}
cur = cur.Next
}
// ---------- 第二轮：根据映射填充所有新节点的 next 和 random ----------
// ⚠️ 注意：map[old.Next] / map[old.Random] 的查找结果若为 nil，直接赋值即可
// 因为 nil pointer 就是 Go 中指针的零值，恰好表示 "不指向任何节点"
for old, new := range mapOldToNew {
new.Next = mapOldToNew[old.Next]
new.Random = mapOldToNew[old.Random]
}
// 返回新链表的头节点
return mapOldToNew[head]
}
[!warning] ⚠️ 两个关键细节
&&不能与:=组合 —— Go 编译器不允许在if的条件表达式中把布尔判断和短变量声明连在一起。必须拆成外层判断 + 内层if + :=的两层结构。nil作为 key 的问题 —— 虽然我们在创建时通过!= nil检查避免了写入 nil key，但遍历时map[old.Next]可能返回 nil（当old.Next == nil时）。这是正确的行为：nil是指针的零值，正好表示"不指向任何节点"，无需额外判空。
方法二：原地交织法 ⭐（O(1) 空间最优解）⭐
/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* Random *Node
* }
*/
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
// ========== 第 1 趟：交织 ==========
// 在每个旧节点后面插入对应的副本
// 目标：A → B → C 变成 A → A' → B → B' → C → C'
cur := head
for cur != nil {
nextTemp := cur.Next // 暂存 B
newNode := &Node{Val: cur.Val}
cur.Next = newNode // A → A'
newNode.Next = nextTemp // A' → B
cur = nextTemp // 移到 B，继续下一轮
}
// ========== 第 2 趟：连接 random ==========
// 因为新节点紧跟在旧节点后面，利用这个关系直接设 random
// 公式：cur'.Random = cur.Random.Next（如果 cur.Random != nil）
// 原因：cur.Random 的副本 cur.Random.Next 恰好就在 cur.Random 后面
cur = head
for cur != nil {
if cur.Random != nil {
cur.Next.Random = cur.Random.Next
}
cur = cur.Next.Next // 每次跳两步，沿旧链表走（A → B → C ...）
}
// ========== 第 3 趟：拆分 ==========
// 把交织在一起的链表拆成两条：原链表和新链表
oldCur := head
newCur := head.Next
newHead := newCur // 保存新链表的头
for oldCur != nil {
// 断开头节点与副本
oldCur.Next = oldCur.Next.Next
// 连接新链表的节点
if newCur.Next != nil {
newCur.Next = newCur.Next.Next
}
// 两指针各前进一步
oldCur = oldCur.Next
newCur = newCur.Next
}
return newHead
}
执行流程可视化（示例 1）：
flowchart TD
INIT["原链表:\n7→13→11→10→1\nrandom: null, →0, →2, →4, →1"]
subgraph Pass1["第1趟：交织"]
P1["7→7'→13→13'→11→11'→10→10'→1→1'"]
end
subgraph Pass2["第2趟：连random"]
P2["7'.random = 7.random.next = nil\n13'.random = 13.random.next = 7'.next = 7' → Wait...\n实际上 13.random指向13自己, so 13'.random = 13.next = 13'\n11'.random = 11.random.next = 10'.next = 10'\n10'.random = 10.random.next = 1'.next = 1'\n1'.random = 1.random.next = 13'.next = 11'"]
end
subgraph Pass3["第3趟：拆分"]
P3["旧链表: 7→13→11→10→1\n新链表: 7'→13'→11'→10'→1'"]
end
INIT --> Pass1 --> Pass2 --> Pass3
style P1 fill:#bbf,stroke:#333
style P2 fill:#f9d,stroke:#333
style P3 fill:#d4edda,stroke:#28a
[!success] ✅ 运行验证 原地交织法是这道题的最优解，在面试中如果能流畅地写出这个解法，说明你对链表操作的掌控达到了相当高的水平。建议掌握以下要点作为面试亮点：① 明确说出三趟遍历的目的；② 能说清楚为什么
cur.Next.Random = cur.Random.Next是正确的；③ 能处理边界情况（nil random、链表为空、单节点）。[!TIP] 💬 面试加分话术 "这道题主要有两种主流解法：哈希表法 O(n) 空间，最直观且不修改原链表；原地交织法 O(1) 空间，最优解。在实际面试中，我会先讲哈希表的思路，因为它最直观、最容易验证正确性。然后告诉面试官我想优化到 O(1) 空间，接着画出交织法的三趟遍历图，说明每一步的不变量是什么——这样做既展示了清晰的思维过程，又体现了对空间复杂度的敏感度。"
[!note] 🤔 如果题目要求不修改原链表怎么办？ 哈希表法天然满足这个约束——它完全没有触碰原链表的任何指针。而原地交织法虽然最终会恢复旧链表，但如果面试官坚持说"原链表绝对不能被修改（哪怕暂时也不行）"，那就只能用哈希表法或者递归法了。