LeetCode LCR 024. 反转链表

2026-03-28 HGNULB 约 6 分钟

文章信息 5 个分类 3 个标签

分类

LeetCode 简单 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 024. 反转链表

题意分析

给定单链表头节点 head，把整条链表的方向反过来，返回反转后的新头节点。要求原地反转指针，而不是重新建一条链表。

全部约束都源自单链表的一条性质：只能沿 next 往后走，拿不到前驱。而反转恰恰要求每个节点指向它原来的前驱，所以必须在遍历过程中自己把前驱「记住」。

由此引出唯一的技术难点——改指针的顺序。一旦执行 p.next = pre，p 原来的后继就再也找不回来，后面整条未处理的链表全部丢失。所以每一步都必须先保存后继，再改指针。

反转后的新头是原链表的最后一个节点，因此返回值不可能是原 head——原 head 反转后变成了尾节点。这是本题最高频的返回值错误。

边界：链表为空返回空；只有一个节点时反转后仍是它自己。好的实现应该让这两种情况自然落入主逻辑，而不是靠额外的特判分支。

解法：LCR处理

核心思路

最容易想到的做法是把所有节点值倒进数组再逆序写回，$O(n)$ 时间但要 $O(n)$ 空间，而且只改了值没改结构，节点若携带其他字段就不成立。瓶颈在于：我们其实不需要「记住所有节点」，只需要在改指针的那一瞬间知道当前节点的前驱和后继，这是两个常数量。

于是维护两个指针：pre 指向已反转部分的头，p 指向待处理部分的头。初始时已反转部分为空，所以 pre = null；待处理部分是整条链表，所以 p = head。

循环不变量是：pre 指向的链表是原链表前若干个节点的反转结果，p 指向的链表是原链表剩余节点且保持原方向，两段完全断开。每轮循环把一个节点从 p 那段的头部搬到 pre 那段的头部，不变量得以维持。

每一轮做四件事：暂存 q = p.next 保住待处理段的入口 → p.next = pre 把 p 接到已反转段前面 → pre = p → p = q。循环在 p == null 时终止，此刻待处理部分为空，pre 就是完整反转链表的头。

pre 的初值取 null 一箭双雕：它既表示「已反转部分为空」，又恰好让原头节点在第一轮之后 next 变成空，自动完成了「原头变尾节点」的断尾。空链表与单节点也因此不需要特判。

解题步骤

初始化：pre = null、p = head。pre 必须是 null 而不是 head，否则原头节点会指向自己形成自环。

循环条件写 p != null：用 p 而不是 p.next 作条件，才能保证最后一个节点也被反转到。

暂存后继：q = p.next 必须是循环体的第一行。这一行是整段代码的安全带，改指针之前先把去路存下来。

翻转当前指针：p.next = pre，把当前节点接到已反转段的头部，它随即成为新的已反转头。

推进两个指针：先 pre = p，再 p = q。两行顺序不能反——先动 p 会让 pre = p 拿到错误的节点。

返回 pre：不是 head（它已是尾节点），也不是 p（此时为 null）。

以 1 → 2 → 3 → null 走一遍，用 | 分隔已反转的 pre 段与待处理的 p 段。初始状态是 null | 1 → 2 → 3。第一轮：暂存 q = 2，执行 1.next = null，推进后得到 1 | 2 → 3，pre 指向 1、p 指向 2。第二轮：暂存 q = 3，执行 2.next = 1，推进后得到 2 → 1 | 3。第三轮：暂存 q = null，执行 3.next = 2，推进后得到 3 → 2 → 1 |，此时 p 为空，循环退出，返回 pre 即节点 3，链表为 3 → 2 → 1 → null。

再看空链表：p 一开始就是 null，循环一次都不进，直接返回初始的 pre = null，正确。单节点 1：一轮之后 1.next 被置为 null（本来也是 null），pre 指向节点 1，p 变空退出，返回节点 1，正确。两个边界都由主逻辑自然覆盖。

代码实现

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, p = head;
        while (p != null) {
            // 改 p.next 之前先保住后继，否则待处理段整体丢失。
            ListNode q = p.next;
            p.next = pre;
            pre = p;
            p = q;
        }
        return pre;
    }
}

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    for p := head; p != nil; {
        // 改 p.Next 之前先保住后继，否则待处理段整体丢失。
        q := p.Next
        p.Next = pre
        pre = p
        p = q
    }
    return pre
}

复杂度分析

时间复杂度：$O(n)$，每个节点恰好被访问并改一次指针，循环体内只有四次赋值，全是常数操作。

空间复杂度：$O(1)$，只用了 pre、p、q 三个指针变量，与链表长度无关；没有开数组，也没有递归栈，这是迭代写法相对递归写法的核心优势。

关键点总结

「改指针前先暂存后继」是链表原地修改的通用铁律，凡是要动 next 的题都先想这一步。

循环不变量「pre 段已反转、p 段未动、两段断开」是理解这四行赋值的钥匙，也是面试官追问时该说出口的话。

pre 初值取 null 同时完成了「已反转段为空」和「原头变尾后 next 置空」两件事，好的初值能省掉一个特判。

只在有限的常数个指针里做文章，就能把「需要前驱」的问题在单链表上解决，这个思路可以直接迁移到区间反转和分组反转。

面试视角：写完主动说明循环不变量和退出时 pre 为何是新头；如果被追问还有没有别的写法，可以提递归版本，同时指出它需要 $O(n)$ 栈空间且因为回溯后还有两步操作而无法尾递归优化。

易错点总结

忘记暂存 q：1 → 2 → 3 在第一轮执行 1.next = null 后节点 2、3 再也访问不到，p = p.next 取到 null 立刻退出，返回只含一个节点的 1。

返回 head 而不是 pre：1 → 2 → 3 会返回 1 → null，因为原头已变成尾节点。

推进顺序写反：先 p = q 再 pre = p，pre 会指向下一个未处理节点，1 → 2 → 3 结果变成断裂的残链。

循环条件写成 p.next != null：最后一个节点不会被反转，1 → 2 → 3 得到 2 → 1 且节点 3 游离在外。

pre 初值写成 head：第一轮 1.next = 1 形成自环，遍历结果时死循环。

返回 p：循环退出时 p 恒为 null，任何非空输入都会返回空链表。

靠交换节点的值来反转：需要额外空间存值，且节点若带有其他字段就完全不成立，题目考的是指针操作而非值搬运。

Go 里把 pre 写成 pre := head：与 Java 版同样形成自环，1 → 2 会得到 1 → 1 的死圈。

相似题目

题目	难度	考察点
206. 反转链表	简单	与本题同题，可直接套用三指针骨架
剑指 Offer 24. 反转链表	简单	与本题同题，可直接套用
92. 反转链表 II	中等	只反转 `[left, right]` 区间，需借哑结点定位前驱并把两端重新接回
25. K 个一组翻转链表	困难	分组反转，每组套用本题骨架，还要处理不足 k 个的尾部保持原序
24. 两两交换链表中的节点	中等	k = 2 的特例，可直接三指针交换，也可套用分组反转的通用解
143. 重排链表	中等	反转只是中间一步，还要先找中点、最后交替合并两条链
234. 回文链表	简单	反转后半段再与前半段逐一比对，可做到 $O(1)$ 空间
2130. 链表最大孪生和	中等	同样是「找中点 + 反转后半段」，但比对时求的是配对和的最大值
面试题 02.06. 回文链表	简单	与 234 同题，反转半链后双指针对比