LeetCode 92. 反转链表 II

约 4 分钟
文章信息 25 个分类 1 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 200-500 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 小米 商汤 旷视 虾皮 哔哩哔哩 小红书 面试经典 150 题
标签
链表
目录

题目描述

✅ 92. 反转链表 II

image-20230226203819078

image-20230226203923748

题意分析

输入是一条单链表以及两个从 1 开始计数的位置 left 与 right，要求把第 left 到第 right 个节点的顺序倒过来，其余节点的相对顺序与取值都保持不变，最后返回整条链表的头节点。

题面给的是「位置」而不是「值」，说明区间端点只能靠一步步计数走到，没有比较或查找的余地；而它保证 1 <= left <= right <= n，意味着区间一定合法，不需要写参数校验。返回类型是节点指针而不是 void，这本身就是一个信号：头节点有可能被换掉。

需要单独想清楚的边界有三种。left = 1 时被反转的区间从头节点开始，原头节点会退到区间尾部，返回值必须是新的头；left = right 时区间只有一个节点，整条链表应当原样返回；right = n 时区间尾部之后没有节点，接线时面对的是空指针而不是一个真实节点。

核心思路

使用哨兵节点统一处理 left = 1。先找到反转区间的前驱 pre，并固定区间首节点 cur；随后重复把 cur.next 摘下，插到 pre 后面。执行 right - left 次后，区间完成原地反转，尾部始终由 cur.next 自动衔接。

解题步骤

  1. 创建哨兵节点 dummy，令 dummy.next = head。
  2. 从 dummy 前进 left - 1 步，找到区间前驱 pre。
  3. 令 cur = pre.next，循环 right - left 次，将 cur.next 头插到 pre 后。
  4. 返回 dummy.next。

复杂度分析

  • 时间复杂度：$O(n)$，最多遍历链表一次。
  • 空间复杂度：$O(1)$，只使用常数个指针。

关键点总结

  • 哨兵节点消除反转区间从链表头开始的特殊处理。
  • pre 和 cur 始终不动，每轮只搬动 cur.next。
  • 循环次数是 right - left；当 left = right 时自然执行 0 次。

易错点总结

  • pre 应停在第 left - 1 个节点，不能多走一步。
  • 修改 cur.next 前必须先保存待移动节点。
  • 头插顺序应为 cur.next = next.next、next.next = pre.next、pre.next = next。
  • 必须返回 dummy.next，否则 left = 1 时会返回旧头节点。

代码实现

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        for (int i = 1; i < left; i++) {
            pre = pre.next;
        }

        ListNode cur = pre.next;
        for (int i = 0; i < right - left; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }
}

func reverseBetween(head *ListNode, left int, right int) *ListNode {
    dummy := &ListNode{Next: head}
    pre := dummy
    for i := 1; i < left; i++ {
        pre = pre.Next
    }

    cur := pre.Next
    for i := 0; i < right-left; i++ {
        next := cur.Next
        cur.Next = next.Next
        next.Next = pre.Next
        pre.Next = next
    }
    return dummy.Next
}

相似题目

题目 难度 考察点
24. 两两交换链表中的节点 中等 区间长度固定为 2，无需定位端点，但反转要沿链反复进行
25. K 个一组翻转链表 困难 把本题的区间反转按 K 分组重复执行，末尾不足 K 的一段不反转
143. 重排链表 中等 反转只是中间步骤，还要先找中点、再把两条链交叉合并
206. 反转链表 简单 区间就是整条链，不需要哨兵、前驱定位和接回
234. 回文链表 简单 反转后半段只为逐位比值，不要求恢复原始链表结构
LCR 024. 反转链表 简单 与 206 同题换皮，用来单独打磨三指针模板本身
LCR 026. 重排链表 中等 与 143 同题换皮，考察中点、反转、归并三步的组合
LCR 027. 回文链表 简单 与 234 同题换皮，重点落在快慢指针定位中点
剑指 Offer 24. 反转链表 简单 与 206 同题换皮，常被额外要求给出递归写法
面试题 02.06. 回文链表 简单 与 234 同题换皮，强调把空间压到 $O(1)$ 的判定方式