跳至主要內容

反转链表II——区间反转的哑节点技巧与指针操控

老张2026/4/30大约 11 分钟

反转链表II——区间反转的哑节点技巧与指针操控

适读人群：有链表基础的 Java 工程师 | 阅读时长：约20分钟 | 难度：Medium

开篇故事

上一篇讲了反转整个链表，有读者问：如果只反转中间一段呢？这个问题问得好，因为面试里考区间反转的频率比反转整个链表还要高——它更能考察候选人的指针控制能力。

我自己第一次做这道题是在笔试里，时间只有45分钟，题目是92题变体。我当时想，不就是定位到区间，然后反转，再把两端接回去吗？结果写了将近30分钟，各种指针接错，第一次提交WA，第二次提交在某个边界用例挂了，第三次才过，已经没时间做后面的题了。

事后复盘，发现核心问题是没有系统化的方法论——靠感觉硬写，必然乱。后来我总结了一个口诀：哑节点打头阵，四个指针不迷路。每次做区间反转，按这个口诀来，基本不会出错。

这篇文章把这套方法讲清楚，同时给出三种解法，包括一种"穿针引线"的技巧，在某些复杂链表题里非常好用。

一、题目解析

题目：LeetCode 92. 反转链表 II

给你单链表的头节点 head 和两个整数 left 和 right，其中 left <= right。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

示例：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

输入：head = [5], left = 1, right = 1
输出：[5]

约束条件：

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

考点梳理：

  1. 如何找到区间的左边界和右边界
  2. 反转区间内的节点
  3. 把反转后的区间重新接回原链表——这步最容易出错
  4. 边界情况：left=1（区间从头开始）、left=right（区间只有一个节点）

第3点是这道题的精髓，也是最容易错的地方。把反转后的片段接回去，需要四个连接点：区间左边界的前一个节点、区间的原始头节点（反转后变成尾节点）、区间的原始尾节点（反转后变成头节点）、区间右边界的后一个节点。

二、解法一：暴力解法——收集节点值翻转

思路

和反转整个链表的暴力思路类似：先找到区间 [left, right] 内的所有节点，把它们的值存到数组里，翻转数组，然后把翻转后的值写回对应节点。

完整代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 收集区间内节点值
        List<Integer> vals = new ArrayList<>();
        ListNode curr = head;
        int pos = 1;
        
        // 找到 left 位置并开始收集
        while (curr != null) {
            if (pos >= left && pos <= right) {
                vals.add(curr.val);
            }
            curr = curr.next;
            pos++;
        }
        
        // 翻转收集到的值
        Collections.reverse(vals);
        
        // 把翻转后的值写回链表中的对应节点
        curr = head;
        pos = 1;
        int idx = 0;
        while (curr != null) {
            if (pos >= left && pos <= right) {
                curr.val = vals.get(idx++);
            }
            curr = curr.next;
            pos++;
        }
        
        return head;
    }
}

复杂度分析

  • 时间复杂度：O(n)。两次遍历链表，每次 O(n)。
  • 空间复杂度：O(right - left + 1) = O(n)。存储区间内的节点值。

适用场景

思路简单，代码容易理解。但在面试中这个解法只能作为兜底方案，面试官一定会追问有没有不修改节点值、只改指针的写法，因为实际工程中节点值可能是复杂对象，直接复制值的代价很高。

三、解法二：优化解法——哑节点 + 四指针反转

思路

这是标准解法。核心是引入一个哑节点（dummy node）统一处理头节点被反转的特殊情况，然后用四个指针精确定位区间。

为什么需要哑节点？

当 left = 1 时，区间从链表头开始，反转后头节点会变化。如果直接操作，需要单独处理这个边界情况，代码会很啰嗦。引入哑节点 dummy，让 dummy.next = head，这样 left 位置的前一个节点始终存在（就是 dummy 或者某个中间节点），不需要特判。

四个关键节点：

  • pre：区间左边界的前一个节点（反转完成后需要 pre.next = 反转后区间的头节点）
  • start：区间的起始节点（即第 left 个节点，反转后变成区间的尾节点）
  • then：反转过程中，start.next 指向的节点（即下一个要移到前面的节点）

反转操作的核心动作（头插法）：

每次把 then 节点摘下来，插到 pre 的后面（即区间头部）。重复 right - left 次。

以 [1,2,3,4,5]，left=2，right=4 为例，逐步演示：

初始：dummy -> 1 -> 2 -> 3 -> 4 -> 5 pre = 节点1，start = 节点2，then = 节点3

第一次操作：把 then(3) 插到 pre(1) 后面

start.next = then.next  (2.next = 4)
then.next = pre.next    (3.next = 2)
pre.next = then         (1.next = 3)
then = start.next       (then = 4)

结果：dummy -> 1 -> 3 -> 2 -> 4 -> 5

第二次操作：把 then(4) 插到 pre(1) 后面

start.next = then.next  (2.next = 5)
then.next = pre.next    (4.next = 3)
pre.next = then         (1.next = 4)
then = start.next       (then = 5)

结果：dummy -> 1 -> 4 -> 3 -> 2 -> 5

完成！共操作 right - left = 2 次。

完整代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 哑节点，统一处理 left=1 的边界情况
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // pre 找到第 left-1 个节点（区间左边界的前一个节点）
        ListNode pre = dummy;
        for (int i = 1; i < left; i++) {
            pre = pre.next;
        }
        
        // start 是区间的起始节点（第 left 个节点）
        ListNode start = pre.next;
        // then 是下一个要被移动到前面的节点
        ListNode then = start.next;
        
        // 执行 right - left 次头插法
        for (int i = 0; i < right - left; i++) {
            start.next = then.next;  // start 跳过 then，指向 then 的后继
            then.next = pre.next;    // then 插到 pre 之后原来的头节点前面
            pre.next = then;         // pre 指向新插入的 then
            then = start.next;       // then 更新为下一个待插入节点
        }
        
        return dummy.next;
    }
}

复杂度分析

  • 时间复杂度：O(n)。找到 pre 最坏 O(n)，反转操作 O(right - left) 次，总体 O(n)。
  • 空间复杂度：O(1)。只用了常数个额外指针。

适用场景

面试标准答案，一次遍历完成，时间空间都是最优。代码量比暴力版本还少，逻辑非常清晰。务必掌握。

四、解法三：最优解法——递归分解

思路

递归思路：把"反转 [left, right] 区间"分解为"反转前 n 个节点"这个子问题。

先实现一个辅助函数 reverseN(head, n)，反转链表的前 n 个节点，并且返回反转后的头节点，同时正确接上第 n+1 个节点。

然后：

  • 如果 left == 1，就是反转前 right 个节点，直接调用 reverseN
  • 如果 left > 1，问题缩减为：对 head.next 执行 reverseBetween(head.next, left-1, right-1)

Mermaid 图——递归调用链

reverseN 的实现要点：

反转前 n 个节点时，需要保存第 n+1 个节点（successor），让反转后区间的尾节点（原来的头节点）指向 successor，而不是 null。

class Solution {
    // 记录区间右边界的后继节点，在递归返回时用于接尾
    private ListNode successor = null;
    
    // 反转链表的前 n 个节点
    private ListNode reverseN(ListNode head, int n) {
        // 只剩最后一个要反转的节点：记录它的后继
        if (n == 1) {
            successor = head.next;
            return head;
        }
        
        // 反转 head.next 开始的前 n-1 个节点
        ListNode newHead = reverseN(head.next, n - 1);
        
        // 把 head 接到反转后链表的末尾
        head.next.next = head;
        // head 不接 null，而是接 successor（第 n+1 个节点）
        head.next = successor;
        
        return newHead;
    }
    
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 区间从头开始，直接用 reverseN
        if (left == 1) {
            return reverseN(head, right);
        }
        
        // 区间不从头开始，递归缩小问题规模
        // head.next 的子链表，区间变为 [left-1, right-1]
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
}

复杂度分析

  • 时间复杂度：O(n)。递归深度最大为 left，reverseN 内部递归深度为 right - left + 1，总计 O(n)。
  • 空间复杂度：O(n)。递归调用栈占用 O(n) 空间。注意 successor 是实例变量，用了额外 O(1) 空间，但递归栈是 O(n) 的。

适用场景

递归版本代码优雅，逻辑分解清晰，展示了将复杂问题拆解为简单子问题的思维方式。面试中写出来并能讲清楚 successor 的作用，是很强的加分项。但生产代码建议用解法二，空间复杂度 O(1) 且无栈溢出风险。

提交结果：时间击败约 100% 用户，空间因递归栈约击败 50% 用户。

五、举一反三

同类题目

LeetCode 25. K 个一组翻转链表 区间反转的升级版，固定每 K 个为一组，本篇的解法二（头插法）可以直接扩展。

LeetCode 24. 两两交换链表中的节点 K=2 的特殊情况，也可以用头插法来做。

LeetCode 206. 反转链表 left=1，right=n 的特殊情况，是本题的基础。

LeetCode 2074. 反转偶数长度组的节点 进阶变体，判断每组长度是否为偶数再决定是否反转，需要灵活运用区间反转。

解题模板

区间反转通用模板（哑节点 + 头插法）：

// 1. 哑节点
ListNode dummy = new ListNode(0);
dummy.next = head;

// 2. 定位区间左边界的前一个节点
ListNode pre = dummy;
for (int i = 1; i < left; i++) pre = pre.next;

// 3. 标记区间起始节点
ListNode start = pre.next;
ListNode then = start.next;

// 4. 头插法反转 (right - left) 次
for (int i = 0; i < right - left; i++) {
    start.next = then.next;
    then.next = pre.next;
    pre.next = then;
    then = start.next;
}

return dummy.next;

这个模板背下来，遇到任何区间反转问题直接套用。

六、踩坑实录

坑一：没有哑节点，left=1 时特殊处理出错

不用哑节点的做法需要单独判断 left == 1 的情况，而且反转完后头节点变了，返回的时候容易忘记返回新头节点。哑节点彻底规避了这个问题，代码更统一。

坑二：头插法四行代码顺序混乱

头插法的四行操作有严格的顺序依赖：

start.next = then.next;  // 必须最先，否则 then.next 被覆盖
then.next = pre.next;    // 必须在 pre.next 修改之前
pre.next = then;         // 修改 pre.next
then = start.next;       // 更新 then

如果把第3行和第4行写反了，then 会变成刚刚插入的节点，进入死循环。

坑三：递归版本忘记设置 successor 导致链表断裂

很多人照着反转整个链表的递归模板来改，忘记了区间反转里尾节点不能指向 null，要指向第 right+1 个节点。漏了这个，后面的链表就全丢了。

坑四：循环次数写错

头插法的循环次数是 right - left 次，不是 right - left + 1 次。以 left=2, right=4 为例，需要移动节点3和节点4，共2次，正好是 4-2=2。

这里经常出现差一错误。我的记忆方法是：区间内有 right-left+1 个节点，第一个节点 start 已经在正确位置了（循环结束后它会成为区间尾节点），所以只需要移动剩余的 right-left 个节点。

坑五：递归版本 successor 是实例变量，多次调用有状态污染

如果把 Solution 的实例复用，successor 可能残留上次调用的值。这在面试中基本不会有问题（LeetCode 每次都新建实例），但在工程代码中如果把这个方法抽出来复用，要注意这个陷阱。建议把 successor 作为局部变量通过方法参数传递，或者用迭代版本规避这个问题。

七、总结

这道题是链表操控能力的试金石。迭代版本（解法二）是面试场上最应该写的方案——O(1) 空间，一次遍历，代码简洁。递归版本展示了更深的思维方式，是学习分解子问题的好例子。

有几点我觉得对后续的链表题很有帮助，记一下：

哑节点是处理头节点变动问题的万能药，只要题目涉及"可能修改头节点"，就加一个哑节点。头插法是区间反转的核心动作，掌握了这四行代码的语义，K组反转（25题）的核心操作就不陌生了。理解了这道题，下一题 25 题就自然通了。

编辑此页
最近更新:
贡献者: xiaozhangge