leetcode-go/链表/23-反转链表.md

tags, create time

tags	create time
LeetCode 链表 双指针 递归 简单	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 为例）：

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 之后。

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 的赋值）：

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 环境内置如下结构体定义：

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-反转链表 — 完全相同的题目
• 92-反转链表 II — 进阶版，只需反转 [m, n] 区间
• 25-K 个一组翻转链表 — 综合应用：分组 + 反转 + 拼接

---

代码

迭代法

/**
 * 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 现在是原链表的最后一个节点，即新头节点
}

头插法（虚拟头节点）

/**
 * 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 是新链表的头节点
}

递归法

/**
 * 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%+。作为链表入门必做题，它的价值不在于难度而在于思维模式的建立——"保存-翻转-推进" 的迭代模式是链表操作的基础范式；而递归版本则展示了如何用函数的调用栈隐式地管理状态。两道实现都值得手写一遍。