链表中等1 种解法

#92反转链表 II

只反转链表从 left 到 right 的闭区间，其余节点位置保持不变。

#链表

解题主线

定位区间前驱后，固定 current 在反转区间尾部，连续把 current.next 头插到区间前端。

每次头插恰好扩大一个已反转节点，执行 right - left 次。

解法 1：区间头插法

走到第 left 个节点的前驱，将区间内后续节点逐个摘下并插到区间最前面。

时间复杂度

O(n)，最坏遍历至 right

空间复杂度

O(1)

92. 反转链表 II · 区间头插法

java

public class Solution {
    static final class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left < 1 || right < left) {
            throw new IllegalArgumentException("invalid interval");
        }
        ListNode dummy = new ListNode(0, head);
        ListNode before = dummy;
        for (int position = 1; position < left; position++) {
            before = before.next;
            if (before == null) throw new IllegalArgumentException("left exceeds list length");
        }
        ListNode current = before.next;
        if (current == null) throw new IllegalArgumentException("left exceeds list length");

        for (int i = 0; i < right - left; i++) {
            ListNode moved = current.next;
            if (moved == null) throw new IllegalArgumentException("right exceeds list length");
            current.next = moved.next;
            moved.next = before.next;
            before.next = moved;
        }
        return dummy.next;
    }
}

走到第 left 个节点的前驱，将区间内后续节点逐个摘下并插到区间最前面。

边界与易错点

原实现默认区间合法，越界会空指针；展示代码显式检查 left、right 与链长。
重连的三步顺序不能交换：先摘 next，再接到区间头，最后更新前驱。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

Q092_ReverseListII.java