LeetCode 206. 反转链表

◎

本节目标

用 prev、cur、nxt 三指针维持已反转与待处理区间，原地反转单链表。

这道题是链表反转解题框架的第一道母题。目标不是背诵四行指针更新，而是能用不变量解释每行代码为什么不会丢节点。

查看原题

题意与约束

给定一条单链表的头节点，把所有节点的连接方向翻转，返回翻转后的新头节点。例如，1 -> 2 -> 3 -> null 应变为 3 -> 2 -> 1 -> null。

输入可以是空链表，也可以只有一个节点。节点值的大小和是否重复都不影响算法，因为我们只改写节点之间的 next 连接，不比较也不修改节点值。

第一反应

看到“单链表原地反转”，第一反应应该是：

1. 把链表分为已反转前缀和待处理后缀；
2. 每轮取下后缀的第一个节点，接到已反转前缀的头部；
3. 因为改写 cur.next 会覆盖后续入口，必须先用第三个指针保存它。

这个模型可以直接得到 O(n) 时间、O(1) 额外空间的迭代解法。

从不变量推导操作顺序

设 prev 指向已反转区间的头，cur 指向待处理区间的头。每轮循环开始时：

• 从 prev 开始能走遍已处理的原链表前缀，顺序已经反转；
• 从 cur 开始能走遍所有未处理节点，顺序仍与原链表相同；
• 两段合起来恰好是原链表的所有节点。

要让该不变量向前推进一个节点，顺序只能是：

nxt = cur.next               // 先保住未处理后缀的入口
cur.next = prev              // 让当前节点指回已反转区间
prev = cur                   // 已反转区间向右扩展一个节点
cur = nxt                    // 待处理区间向右收缩一个节点

如果先执行 cur.next = prev，原来指向后续节点的唯一连接就被覆盖。没有事先保存的 nxt，后续节点会从可达结构中丢失。

逐步演示

以 1 -> 2 -> 3 -> null 为例：

时刻	prev 引出的已反转区间	cur 引出的待处理区间	本轮保存的 nxt
初始	null	1 -> 2 -> 3 -> null	尚未保存
处理 1 后	1 -> null	2 -> 3 -> null	曾保存节点 2
处理 2 后	2 -> 1 -> null	3 -> null	曾保存节点 3
处理 3 后	3 -> 2 -> 1 -> null	null	保存为 null

当 cur 变为 null 时，待处理区间已空，全部节点都位于已反转区间。不变量因此直接证明：返回 prev 即可。

代码实现

两份源码使用完全相同的迭代算法和指针更新顺序。页面通过 raw loader 直接展示自动测试所编译、执行的源文件，因此文档中不存在另一份可能漂移的代码。

C++

C++17

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            // 保存后继节点
            ListNode* nxt = cur->next;
            // 反转指向
            cur->next = prev;
            // 推进边界
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
};

Python

Python 3

class Solution:
    def reverseList(self, head):
        prev = None
        cur = head
        while cur is not None:
            # 保存后继节点
            nxt = cur.next
            # 反转指向
            cur.next = prev
            # 推进边界
            prev = cur
            cur = nxt
        return prev

C++ 中的 nullptr 与 Python 中的 None 都表示空的已反转区间。两种语言统一使用 prev、cur、nxt；nxt 只在改写 cur.next 前暂存后继节点。

复杂度分析

• 时间复杂度：O(n)。每个节点恰好成为一次 cur，每轮只做常数次指针读写。
• 额外空间：O(1)。无论链表多长，都只维护 prev、cur、nxt 三个指针。

边界与易错点

• 空链表：初始时 cur 就为空，循环不执行，返回为空的 prev。
• 单节点链表：唯一一轮中 nxt 为空，节点继续指向空，最后返回该节点。
• 保存顺序：必须在覆盖 cur.next 之前保存后续入口，否则剩余链表会丢失。
• 边界移动顺序：必须先让 prev 接管当前节点，再让 cur 移到 nxt。
• 返回值：循环结束时 cur 为空，新链表的头是 prev，不是原 head。
• 环的风险：若只把某个节点指回前驱，却没有按模板继续移动边界，可能保留旧连接而形成环。

自动测试覆盖空链表、单节点链表以及含五个节点的普通链表，并对两种语言验证相同输出。

迁移到局部反转

整体反转从原头节点开始，直到 cur == null；局部反转仍使用同一组四步操作，只是要先定位边界、限制轮数，再把区间接回原链表。为统一处理 left = 1，先建立虚拟头节点 dummy，令 dummy.next = head。

1. 从 before = dummy 起步，向后移动 left - 1 次。此时 before 一定是区间前驱，不必为头部区间单独分支。
2. 在反转前明确初始化 prev = null、cur = before.next，并保存 segment_tail = cur。区间左端在反转后会成为区间尾。
3. 恰好执行 right - left + 1 轮，每轮仍按四步操作：先保存 nxt = cur.next，再令 cur.next = prev，随后移动 prev = cur 和 cur = nxt。
4. 循环结束后，prev 是区间新头，cur 是区间后继。先接区间尾，再接区间头：执行 segment_tail.next = cur，再执行 before.next = prev，最后返回 dummy.next。

反转第一步会切断区间左端原有的向后连接；两端重连则分别恢复“区间尾到后继”和“前驱到区间新头”。这样不会遗留一条旧方向的边与新反向边互相闭合，因此能避免成环。局部反转不是另一种算法，而是“同一段内不变量 + 明确边界 + 两端重连”；掌握后即可继续迁移到 k 个一组的分组反转。