206. 反转链表#

为什么这道题如此重要#

反转链表看似简单，却是链表操作的基石。就像建房子要先打好地基，做复杂的链表操作前必须深刻理解反转原理。无数高频面试题都建立在这个基础之上：K个一组反转链表、判断回文链表、链表重排序等等。真正理解了反转链表，这些题目就会迎刃而解。

问题描述#

题目目标#

LeetCode第206题”反转链表”要求：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

示例 1#

输入： 1 → 2 → 3 → 4 → 5 输出： 5 → 4 → 3 → 2 → 1 链表示意：

输入:  1 -> 2 -> 3 -> 4 -> 5 -> null
输出:  5 -> 4 -> 3 -> 2 -> 1 -> null

说明： 箭头方向全部反转后，链表顺序就变成了 5 -> 4 -> 3 -> 2 -> 1。

补充说明#

• 链表题的输入本质上是节点之间的连接关系，重点通常是返回处理后的头节点或目标节点。

递归解法：从简单说起#

递归法虽然不是最优解，但它的思路最容易理解。想象你在玩多米诺骨牌，先把所有骨牌排好，然后从最后一张开始，一张张往回推。

递归的本质#

递归反转的核心思想是：

1. 先假设子问题已经解决（后面的链表已经反转完成）
2. 然后解决当前节点如何与已反转部分衔接的问题

就像你要完成一个大项目，不用考虑下属如何完成他们的任务，你只需要考虑如何把大家的工作整合起来。

代码实现和详解#

public ListNode reverseList(ListNode head) {
    // 递归终止条件：空链表 或 只有一个节点 时无需反转，原样返回
    if (head == null || head.next == null) {
        return head;
    }

    // 递归处理 head.next 开始的子链表
    // newHead 始终指向“子链表反转后的新头节点”
    ListNode newHead = reverseList(head.next);

    // 回溯阶段做指针翻转：
    // 原来是 head -> head.next，现在改为 head.next -> head
    head.next.next = head;
    // 把当前节点的 next 断开，避免形成环（例如 2<->3）
    head.next = null;

    // 返回整个反转后链表的新头
    return newHead;
}

迭代解法：追求空间最优#

迭代法虽然理解起来较难，但它是空间复杂度最优的解法。让我们通过一个生活场景来深入理解。

通过生活场景理解迭代#

想象你是一个体操教练，正在教一排学生做”后滚翻”。每个学生原本都面向前方，你要让他们一个接一个地转身。关键是：每处理一个学生时，要确保：

1. 这个学生不会摔倒（保存next指针）
2. 他能拉住前一个学生的手（指向prev）
3. 准备好扶住下一个学生（移动指针）

代码实现和图解#

public ListNode reverseList(ListNode head) {
    // prev：已反转部分的头节点；初始为空，表示已反转部分还不存在
    ListNode prev = null;
    // curr：当前待处理节点，从原链表头开始
    ListNode curr = head;

    while (curr != null) {
        // nextTemp：暂存原链表中 curr 的后继，防止改指针后“断链”
        ListNode nextTemp = curr.next;

        // 将当前节点指向已反转部分的头，实现局部反转
        curr.next = prev;

        // 双指针整体前移：
        // 1) prev 前进到当前节点（扩展已反转区）
        prev = curr;
        // 2) curr 前进到下一待处理节点
        curr = nextTemp;
    }

    // curr 走到 null 时，prev 就是新链表头
    return prev;
}

迭代法的过程图解#

以1→2→3→4→5为例：

初始状态：
prev = null, curr = 1
null ← 1 → 2 → 3 → 4 → 5

第一次迭代后：
prev = 1, curr = 2
null ← 1    2 → 3 → 4 → 5

第二次迭代后：
prev = 2, curr = 3
null ← 1 ← 2    3 → 4 → 5

最终状态：
null ← 1 ← 2 ← 3 ← 4 ← 5

深入理解的关键点#

1. 指针操作的本质#

每次操作都是在改变一个节点的”指向”。就像改变一个人的视线方向，原本看着前方，现在要回头看。

2. 迭代法的不变量#

在任何时刻：

• prev指向的是已完成反转的部分
• curr指向正在处理的节点
• nextTemp保存着待处理的部分

3. 为什么需要三个指针#

• prev：没有它，就不知道往哪里指
• curr：没有它，就不知道现在处理谁
• nextTemp：没有它，就会断链找不到后续节点

实战应用#

这个基础算法在很多场景中都有应用：

1. 需要倒序处理链表时
2. 需要判断链表是否回文时
3. 需要按组反转链表时
4. 需要重排链表时

小结#

掌握链表反转需要：

1. 理解递归和迭代两种思路的本质
2. 深入理解指针操作的含义
3. 反复练习直至形成肌肉记忆
4. 学会用生活场景类比，加深理解

建议：每天默写一遍这道题，直到闭着眼睛也能写对。因为它是链表操作中最基础也是最关键的操作，掌握了它，其他链表问题都会变得容易很多！