600 lines
23 KiB
Markdown
600 lines
23 KiB
Markdown
---
|
||
tags: ["LeetCode", "链表", "哈希表", "原地操作", "中等"]
|
||
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^4`
|
||
- `Node.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 指向错误的副本。必须依赖**引用/地址关系**而非值。
|
||
|
||
整个过程分为两轮遍历：
|
||
|
||
**第一轮：创建所有新节点并建映射**
|
||
|
||
```mermaid
|
||
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 指针**
|
||
|
||
```mermaid
|
||
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 映射可以通过地址关系直接推导出来。
|
||
|
||
#### 三步走策略
|
||
|
||
```mermaid
|
||
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 之间。
|
||
|
||
```go
|
||
// 伪代码
|
||
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'`）：**
|
||
|
||
```mermaid
|
||
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 的副本恰好在它后面）
|
||
|
||
**图解：**
|
||
|
||
```mermaid
|
||
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' 后续的连接，所以需要分别维护两条链的尾指针。
|
||
|
||
```go
|
||
// 伪代码
|
||
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'` 拆开）：**
|
||
|
||
```mermaid
|
||
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 中会编译报错：
|
||
> ```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 环境内置如下结构体定义：
|
||
|
||
```go
|
||
type Node struct {
|
||
Val int
|
||
Next *Node
|
||
Random *Node
|
||
}
|
||
```
|
||
|
||
不需要手动定义，直接在解题中使用即可。
|
||
|
||
> [!info] 📊 两种方法对比
|
||
|
||
| 维度 | 哈希表法（迭代） | 原地交织法 ⭐ |
|
||
|------|---------|-------------|
|
||
| 时间复杂度 | O(n) | O(n) |
|
||
| 空间复杂度 | O(n) | O(1) |
|
||
| 代码行数 | ~25 行 | ~25 行 |
|
||
| 直观程度 | 很高（直接建映射） | 中等（需理解三趟遍历的意图） |
|
||
| 面试推荐 | ⭐⭐ 可作为铺垫讲出 | ⭐⭐⭐ 面试官期望的答案 |
|
||
| 是否修改原链表 | ❌ 完全不改 | ⚠️ 中途改了 next，最终恢复 |
|
||
|
||
> [!success] ✅ 相关题目串联
|
||
> - [22-相交链表](./22-相交链表.md) — 同样是链表上建立映射的经典场景
|
||
> - [146-LRU 缓存](./146-lru-cache.md) — 哈希表 + 双向链表的组合，也是"用哈希加速链表操作"的思路
|
||
> - [24-回文链表](./24-回文链表.md) — 同样使用了"原地操作+反转"的模式来做到 O(1) 空间
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### 方法一：哈希表法（最直观）⭐
|
||
|
||
```go
|
||
/**
|
||
* 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] ⚠️ 两个关键细节
|
||
> 1. **`&&` 不能与 `:=` 组合** —— Go 编译器不允许在 `if` 的条件表达式中把布尔判断和短变量声明连在一起。必须拆成外层判断 + 内层 `if + :=` 的两层结构。
|
||
> 2. **`nil` 作为 key 的问题** —— 虽然我们在创建时通过 `!= nil` 检查避免了写入 nil key，但遍历时 `map[old.Next]` 可能返回 nil（当 `old.Next == nil` 时）。这是正确的行为：`nil` 是指针的零值，正好表示"不指向任何节点"，无需额外判空。
|
||
|
||
---
|
||
|
||
### 方法二：原地交织法 ⭐（O(1) 空间最优解）⭐
|
||
|
||
```go
|
||
/**
|
||
* 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）：**
|
||
|
||
```mermaid
|
||
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] 🤔 如果题目要求不修改原链表怎么办？
|
||
> 哈希表法天然满足这个约束——它完全没有触碰原链表的任何指针。而原地交织法虽然最终会恢复旧链表，但如果面试官坚持说"原链表绝对不能被修改（哪怕暂时也不行）"，那就只能用哈希表法或者递归法了。
|