LeetCode 剑指 Offer 24. 反转链表

约 4 分钟
文章信息 15 个分类 2 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 10-20 字节跳动 微软 阿里巴巴 快手 腾讯 猿辅导 哔哩哔哩 剑指 Offer 剑指 Offer（第 2 版）
标签
链表 递归
目录

题目描述

✅ 剑指 Offer 24. 反转链表

image-20241107205301819

题意分析

题目给的是一个单向链表的头指针，要求返回反转之后的头指针。反转的含义是：原来第一个节点变成最后一个，原来最后一个变成第一个，节点本身不变，变的是每个节点的 next 指向。

约束里有两个关键信号。第一，这是单向链表，只能沿着 next 往后走，拿不到任何节点的前驱，也不能像数组那样按下标随机访问；想知道「谁应该是我的新后继」，只能靠自己一路走一路记。第二，只给了头指针，没给长度，所以事先并不知道尾节点在哪里，只能靠「走到 null」来判断结束。

返回值必须是新的头指针，也就是原链表的尾节点，这一点很容易被忽略：反转之后原来的 head 会退化成尾节点，直接返回它只会得到一个长度为 1 的链表。

边界情况有两类：空链表，此时应当返回空；只有一个节点的链表，此时反转前后完全相同。好的写法应该让这两种情况自然落在主循环里，而不需要额外的特判分支。

解法：迭代三指针反转

核心思路

单链表无法回头，所以遍历到 cur 时必须同时保存它的前驱 pre 和原后继 next。每轮只做一次局部反转：先保存 cur.next，再令 cur.next = pre，最后让两个工作指针向前移动。

循环不变量：每轮开始时，pre 是已经反转完成的前缀头节点，cur 是尚未处理的后缀头节点；两段合起来恰好包含原链表全部节点。初始时已反转段为空；循环结束时未处理段为空，因此 pre 就是新头节点。

解题步骤

  1. 初始化 pre = null、cur = head。pre 为空可保证原头节点最终成为尾节点并指向空。
  2. 在改写指针前，用 next 保存 cur.next，否则未处理后缀会丢失。
  3. 执行 cur.next = pre，把当前节点接到已反转前缀之前。
  4. 依次更新 pre = cur、cur = next，继续处理后缀。
  5. cur == null 时返回 pre。

以 1 → 2 → 3 为例，三轮结束后的已反转段依次是 1、2 → 1、3 → 2 → 1，最终返回节点 3。

代码实现

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            // 当前节点指回已经反转好的前半部分。
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    for cur != nil {
        next := cur.Next
        // 保存 next 后再改变指针方向。
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点恰好处理一次。
  • 空间复杂度：$O(1)$，只使用 pre、cur、next 三个指针，直接修改原链表。

关键点总结

  • 指针操作顺序固定：保存后继、反转当前边、移动两个工作指针。
  • pre 始终指向已反转前缀，cur 始终指向未处理后缀。
  • 返回 pre，因为原 head 已成为尾节点，退出时 cur 已为空。
  • 面试追问递归版时要指出：时间仍是 $O(n)$，但调用栈需要 $O(n)$，不如迭代版稳定。

易错点总结

  • 先改 cur.next 再保存后继，会立即断开未处理链表；必须先保存 next。
  • 循环条件写成 cur.next != null 会漏掉最后一个节点，并在空链表上空指针；应判断 cur != null。
  • pre 初始为 head 会让第一个节点指向自身形成环；它必须从 null 开始。
  • 返回原 head 只能得到反转后的尾节点；正确返回值是 pre。

相似题目

题目 难度 考察点
206. 反转链表 简单 同题不同题号，可对照迭代与递归两版
92. 反转链表 II 中等 只反转指定区间，需要接回前后两段
25. K 个一组翻转链表 困难 分组反转，不足 k 个时保持原序
24. 两两交换链表中的节点 中等 相邻节点两两交换的哑节点写法
143. 重排链表 中等 找中点、反转后半段、交替合并
234. 回文链表 简单 反转半条链表后做逐位比较
61. 旋转链表 中等 成环后按偏移量重新断开