414 lines
14 KiB
Markdown
414 lines
14 KiB
Markdown
---
|
||
tags: ["LeetCode", "链表", "双指针", "递归", "简单"]
|
||
create time: 2026-05-16 14:35
|
||
---
|
||
|
||
# 23-反转链表
|
||
|
||
## 题面
|
||
|
||
给你单链表的头节点 `head`，请你反转链表，并返回反转后的链表。
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：head = [1,2,3,4,5]
|
||
输出：[5,4,3,2,1]
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：head = [1,2]
|
||
输出：[2,1]
|
||
```
|
||
|
||
**示例 3（空链表）：**
|
||
|
||
```
|
||
输入：head = []
|
||
输出：[]
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- 链表中节点的数目范围是 `[0, 5000]`
|
||
- `-5000 <= Node.val <= 5000`
|
||
- **进阶：** 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 核心洞察
|
||
> 反转链表就是让每条边的方向"掉头"——原来的 `A → B` 变成 `A ← B`。直观来看，我们需要把每个节点的 `next` 指针指向上一个节点。
|
||
|
||
### 关键问题：断链风险
|
||
|
||
> [!warning] ⚠️ 最大陷阱
|
||
> 当你把 `node.next` 改成指向前驱时，你就**丢失了原来 `node.next` 指向的后继节点**。一旦丢失，整条链的后续部分再也找不到了。
|
||
|
||
所以反转的本质操作是三步：
|
||
|
||
| 步骤 | 动作 | 目的 |
|
||
|------|------|------|
|
||
| ① | **保存后继**：记住 `node.next` | 防止断链 |
|
||
| ② | **反转指针**：把 `node.next` 指向前驱 | 完成方向翻转 |
|
||
| ③ | **前移窗口**：把前驱和当前指针各走一步 | 继续处理下一个节点 |
|
||
|
||
### 方法一：迭代法 — 三指针滑动窗口 ⭐（最优）
|
||
|
||
维护三个变量：`prev`（已反转部分的尾部 / 新方向的前驱）、`curr`（正在处理的节点）、`nextTemp`（临时保存后继）。
|
||
|
||
**初始化：**
|
||
|
||
- `prev = nil` — 反转后原头节点的 `next` 将指向 `nil`
|
||
- `curr = head` — 从原头节点开始逐个处理
|
||
|
||
**每一步的操作（以节点 1→2→3→4→5 为例）：**
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph 原始状态
|
||
P["prev: nil"]
|
||
C["curr: 1"]
|
||
N["nextTemp ← 2"]
|
||
end
|
||
|
||
subgraph 反转操作
|
||
R1["1.next = prev → nil"]
|
||
end
|
||
|
||
subgraph 窗口前移
|
||
PM["prev = 1"]
|
||
CM["curr = 2"]
|
||
end
|
||
|
||
P --> C
|
||
C --> N
|
||
N -.引导.-> R1
|
||
R1 -.-> PM
|
||
PM --> CM
|
||
|
||
style C fill:#f9d,stroke:#333
|
||
style R1 fill:#bfb,stroke:#333
|
||
style CM fill:#bbf,stroke:#333
|
||
```
|
||
|
||
逐步展开完整过程：
|
||
|
||
| 步骤 | prev | curr | nextTemp (操作前) | 执行：curr.next = prev |
|
||
|------|------|------|--------------------|----------------------|
|
||
| 初始 | nil | 1 | — | — |
|
||
| 第 1 轮 | 1 | 2 | 2 | 1.next → nil |
|
||
| 第 2 轮 | 2 | 3 | 3 | 2.next → 1 |
|
||
| 第 3 轮 | 3 | 4 | 4 | 3.next → 2 |
|
||
| 第 4 轮 | 4 | 5 | 5 | 4.next → 3 |
|
||
| 第 5 轮 | 5 | nil | — | 5.next → 4 |
|
||
|
||
当 `curr == nil` 时遍历结束，返回 `prev`（即新的头节点 5）。
|
||
|
||
> [!note] 🤔 为什么返回 `prev` 而不是 `curr`？
|
||
> 循环结束时 `curr` 已经走到了 `nil`（原链表末尾之后），而 `prev` 恰好停在最后一个有效节点上——它就是反转后的新头节点。可以用 `curr != nil` 代替终止条件，但代码会稍显冗余（需要最后再走一步）。
|
||
|
||
**时间复杂度：O(n)** — 每个节点只遍历一次。
|
||
**空间复杂度：O(1)** — 只用了三个指针变量。
|
||
|
||
### 方法二（精简版）：虚拟头节点 + 头插法 ⭐（更简洁的迭代法）
|
||
|
||
> [!question] 💡 引导思考
|
||
> 刚才的三指针法需要 `prev` / `curr` / `nextTemp` 三个变量。但如果我们用一个虚拟头节点 `dummy`，让 `dummy.Next` **自动维护已反转部分的头部**，是不是就可以少维护一个变量？
|
||
|
||
这正是经典的**头插法**——每从原链表取出一个节点，就把它插入到 `dummy` 之后。
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph 初始化
|
||
D["dummy → nil"]
|
||
H["head → 1 → 2 → 3 → nil"]
|
||
end
|
||
|
||
subgraph 第1轮
|
||
D2["dummy → 1"]
|
||
H2["head → 2 → 3 → nil"]
|
||
D2 -.head插入后.-> H2
|
||
end
|
||
|
||
subgraph 第2轮
|
||
D3["dummy → 2 → 1"]
|
||
H3["head → 3 → nil"]
|
||
D3 -.head插入后.-> H3
|
||
end
|
||
|
||
subgraph 第3轮
|
||
D4["dummy → 3 → 2 → 1"]
|
||
H4["head = nil"]
|
||
D4 -.head插入后.-> H4
|
||
end
|
||
|
||
D --> D2 --> D3 --> D4
|
||
style D4 fill:#4c4,stroke:#333
|
||
```
|
||
|
||
**核心洞察：** `dummy.Next` 始终等于上一轮的 `prev`！它天然维护着反转部分的头部引用，所以不需要单独声明 `prev`。
|
||
|
||
每轮只需要三个动作（四行代码中的前三行为一组）：
|
||
|
||
| 步骤 | 代码 | 说明 |
|
||
|------|------|------|
|
||
| ① | `temp := head.Next` | 保存后继 |
|
||
| ② | `head.Next = dummy.Next` | 断开原链表，指向已反转部分 |
|
||
| ③ | `dummy.Next = head` | **头插**：把 head 插到 dummy 之后 |
|
||
| ④ | `head = temp` | 继续处理下一个 |
|
||
|
||
以 `1→2→3→nil` 为例：
|
||
|
||
| 轮次 | dummy 之后的链表 | head | temp | 执行的动作 |
|
||
|------|-------------------|------|------|-----------|
|
||
| 初始 | nil | 1 | — | — |
|
||
| 第 1 轮 | **1** → nil | 2 | 3 | 1 插入 dummy 后 |
|
||
| 第 2 轮 | **2** → 1 → nil | 3 | nil | 2 插到 1 前面 |
|
||
| 第 3 轮 | **3** → 2 → 1 → nil | nil | — | 3 插到 2 前面 |
|
||
|
||
循环结束时返回 `dummy.Next`，即反转后的新头节点。
|
||
|
||
> [!tip] 🔑 对比三指针法
|
||
> | 维度 | 三指针法 | 头插法 |
|
||
> |------|---------|--------|
|
||
> | 额外变量 | prev, curr, nextTemp（3 个） | dummy, head, temp（3 个，但 head 是输入参数可复用） |
|
||
> | 核心思路 | 逐个翻转指针方向 | **逐个摘除并头插到新链表** |
|
||
> | 代码行数 | 5 行（循环体内） | 4 行（循环体内） |
|
||
> | 直观程度 | 较抽象（指向前驱） | **最直观**（就是"拔出来插回去"） |
|
||
|
||
**时间复杂度：O(n)** — 每个节点恰好被处理一次。
|
||
**空间复杂度：O(1)** — 只用了两个局部指针变量（head 可复用）。
|
||
|
||
> [!note] 🤔 为什么头插法和三指针法结果一样但中间过程不同？
|
||
> 三指针法是原地修改指针方向（像翻多米诺骨牌），头插法则是把节点逐个摘下来重新挂到新位置。虽然路径不同，但最终效果等价——都让每条边的方向掉转了。头插法之所以不会导致断链，是因为每步操作前都用 `temp` 保存了后继，且 `head.Next = dummy.Next` 这步先于 `dummy.Next = head`，保证了已反转部分不会被切断。
|
||
|
||
### 方法三：递归法（自底向上）
|
||
|
||
递归的核心思想：**把「反转整个链表」分解为「反转剩余部分 + 调整当前节点」**。
|
||
|
||
考虑链表 `1 → 2 → 3 → 4 → 5 → nil`：
|
||
|
||
> [!question] 💡 递归的两个阶段
|
||
> 1. **递（深入）**：一直往深处走，直到遇到基准情况
|
||
> 2. **归（回溯）**：在返回的过程中逐层反转指针
|
||
|
||
**基准情况：** 当 `head == nil` 或 `head.Next == nil` 时，直接返回 `head`（空链表或单节点无需反转）。
|
||
|
||
**递的过程（不断深入到最后）：**
|
||
|
||
```
|
||
reverseList(1) → reverseList(2) → reverseList(3) → reverseList(4) → reverseList(5)
|
||
↑
|
||
遇到基准情况，返回 5（新头节点）
|
||
```
|
||
|
||
**归的过程（逐层反转，注意箭头方向表示 node.next 的赋值）：**
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
L5["5"] -->|返回新头| L4["4"]
|
||
L4 -->|"4.next.Next = 4"| L4B["5 → 4"]
|
||
L4B -->|"4.next = nil"| L4C["5 → 4 → nil"]
|
||
L4C -->|"下一层: 3.next.Next = 3"| L3B["5 → 4 → 3"]
|
||
L3B -->|"3.next = nil"| L3C["5 → 4 → 3 → nil"]
|
||
L3C -->|"下一层: 2.next.Next = 2"| L2B["5 → 4 → 3 → 2"]
|
||
L2B -->|"2.next = nil"| L2C["5 → 4 → 3 → 2 → nil"]
|
||
L2C -->|"下一层: 1.next.Next = 1"| L1B["5 → 4 → 3 → 2 → 1"]
|
||
L1B -->|"1.next = nil"| L1C["5 → 4 → 3 → 2 → 1 → nil"]
|
||
|
||
style L4 fill:#f9d,stroke:#333
|
||
style L1C fill:#4c4,stroke:#333
|
||
```
|
||
|
||
用 `1 → 2 → 3` 简化演示关键步骤：
|
||
|
||
| 阶段 | 递归栈状态 | 链表结构 | 执行的操作 |
|
||
|------|-----------|---------|-----------|
|
||
| 递到最深 | `reverse(3)` 返回 3 | `1 → 2 → 3` | 基准情况，返回 head=3 |
|
||
| 回溯第 1 层 | `reverse(2)` 中 `last=3` | `1 → 2 → 3` | `2.Next.Next = 2` → `3 → 2`；`2.Next = nil` |
|
||
| 回溯第 2 层 | `reverse(1)` 中 `last=3` | `3 → 2 → nil, 1 → 2` | `1.Next.Next = 1` → `2 → 1`；`1.Next = nil` |
|
||
|
||
最终得到 `3 → 2 → 1 → nil`，返回新头节点 3。
|
||
|
||
> [!info] 🧠 递归的关键理解点
|
||
> 每一层递归返回的都是**同一个值**——最开始那个基准情况返回的新头节点（原链表的尾节点）。所有层共享这个返回值，不需要重新拼接。真正发生变化的只是中间各层的 `node.Next` 指针方向。
|
||
|
||
**时间复杂度：O(n)** — 每层 O(1)，共 n 层。
|
||
**空间复杂度：O(n)** — 递归调用栈深度为 n。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
### 迭代法伪代码
|
||
|
||
```
|
||
prev = nil
|
||
curr = head
|
||
|
||
while curr != nil {
|
||
nextTemp = curr.Next // ① 保存后继
|
||
curr.Next = prev // ② 反转指针
|
||
prev = curr // ③ 前移：prev 往前走
|
||
curr = nextTemp // ③ 前移：curr 也往前走
|
||
}
|
||
|
||
return prev // prev 是新头节点
|
||
```
|
||
|
||
### 头插法伪代码
|
||
|
||
```
|
||
dummy = &ListNode{} // 虚拟头节点
|
||
|
||
while head != nil {
|
||
temp := head.Next // ① 保存后继
|
||
head.Next = dummy.Next // ② 断开原链表，指向已反转部分
|
||
dummy.Next = head // ③ 头插：插入到 dummy 之后
|
||
head = temp // ④ 继续处理下一个
|
||
}
|
||
|
||
return dummy.Next // dummy.Next 是新头节点
|
||
```
|
||
|
||
### 递归法伪代码
|
||
|
||
```
|
||
func reverse(head):
|
||
if head == nil or head.Next == nil:
|
||
return head // 基准情况
|
||
|
||
last = reverse(head.Next) // 递：反转剩余部分
|
||
|
||
// 归：反转当前节点与后继之间的边
|
||
head.Next.Next = head // 后继指向当前
|
||
head.Next = nil // 当前指向 nil
|
||
|
||
return last // 始终返回新头节点
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 迭代法口诀：三步走
|
||
> 记不住顺序？想 **"save → flip → advance"**（三指针法）或 **"摘 → 插 → 走"**（头插法）。Go 语言中的三变量交换非常自然，没有额外的临时声明开销。
|
||
|
||
> [!tip] 🔑 递归法记忆法："别人帮我搞定后半段，我只管调头自己这条边"
|
||
> 递归模板适用于大量链表/树问题——`last = recur(rest)` → `调整当前关系` → `return last`。常见变体包括：反转链表 II（区间反转）、两两交换节点、K 个一组翻转等。
|
||
|
||
> [!note] 🐹 Go 中的链表定义
|
||
> LeetCode 的 Go 环境内置如下结构体定义：
|
||
|
||
```go
|
||
type ListNode struct {
|
||
Val int
|
||
Next *ListNode
|
||
}
|
||
```
|
||
|
||
不需要手动定义，直接在解题中使用即可。
|
||
|
||
> [!info] 📊 三种方法对比
|
||
|
||
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|
||
|------|-----------|-----------|------|------|
|
||
| 三指针迭代 ⭐ | O(n) | O(1) | 原地操作、最经典 | 需要维护 prev / curr / nextTemp |
|
||
| **头插法 ⭐** | **O(n)** | **O(1)** | **代码最短（循环体 4 行）、最直观** | 需理解 dummy.Next 的维护逻辑 |
|
||
| 递归法 | O(n) | O(n) | 代码简洁、逻辑清晰 | 深度大时可能栈溢出 |
|
||
|
||
> [!success] ✅ 相关题目串联
|
||
> - [剑指 Offer 24-反转链表](../剑指Offer/) — 完全相同的题目
|
||
> - [92-反转链表 II](./92-反转链表-II.md) — 进阶版，只需反转 [m, n] 区间
|
||
> - [25-K 个一组翻转链表](./25-K-grouper-reverse.md) — 综合应用：分组 + 反转 + 拼接
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### 迭代法
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func reverseList(head *ListNode) *ListNode {
|
||
var prev *ListNode // 初始为 nil，反转后原头节点的 Next 指向 nil
|
||
curr := head
|
||
|
||
for curr != nil {
|
||
nextTemp := curr.Next // ① 保存后继，防止断链
|
||
curr.Next = prev // ② 反转指针：当前节点指向前驱
|
||
prev = curr // ③ prev 前进到当前位置
|
||
curr = nextTemp // ③ curr 前进到保存的后继位置
|
||
}
|
||
|
||
return prev // prev 现在是原链表的最后一个节点，即新头节点
|
||
}
|
||
```
|
||
|
||
### 头插法（虚拟头节点）
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func reverseList(head *ListNode) *ListNode {
|
||
dummy := &ListNode{} // 虚拟头节点，dummy.Next 自动维护已反转部分的头部
|
||
|
||
for head != nil {
|
||
temp := head.Next // ① 保存后继，防止断链
|
||
head.Next = dummy.Next // ② 断开原链表，指向已反转部分
|
||
dummy.Next = head // ③ 头插：把 head 插入到 dummy 之后
|
||
head = temp // ④ 继续处理下一个
|
||
}
|
||
|
||
return dummy.Next // dummy.Next 是新链表的头节点
|
||
}
|
||
```
|
||
|
||
### 递归法
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func reverseList(head *ListNode) *ListNode {
|
||
// 基准情况：空链表或只有一个节点
|
||
if head == nil || head.Next == nil {
|
||
return head
|
||
}
|
||
|
||
// 递归反转剩余部分，last 始终是新的头节点（原链表的尾节点）
|
||
last := reverseList(head.Next)
|
||
|
||
// 反转当前节点 head 和其后继 head.Next 之间的边
|
||
head.Next.Next = head // 后继节点的 Next 指回当前节点
|
||
head.Next = nil // 断开原方向的边
|
||
|
||
return last
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 206 题，通过率约 75%+。作为链表入门必做题，它的价值不在于难度而在于**思维模式的建立**——"保存-翻转-推进" 的迭代模式是链表操作的基础范式；而递归版本则展示了如何用函数的调用栈隐式地管理状态。两道实现都值得手写一遍。
|