链表中等1 种解法
#92反转链表 II
只反转链表从 left 到 right 的闭区间，其余节点位置保持不变。
#链表
原题
给你单链表的头指针head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1 输出：[5]
提示：
- 链表中节点数目为
n 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
解题主线
- 定位区间前驱后，固定 current 在反转区间尾部，连续把 current.next 头插到区间前端。
- 每次头插恰好扩大一个已反转节点，执行 right - left 次。
解法 1：区间头插法
走到第 left 个节点的前驱，将区间内后续节点逐个摘下并插到区间最前面。
-
时间复杂度： O(n)，最坏遍历至 right
-
空间复杂度： O(1)
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) {
// 哨兵节点统一处理 left 为 1 时区间前驱不存在的边界。
// before 固定在区间前，current 固定为反转后区间尾节点。
// 每轮摘下 current.next 并头插，已反转区间恰好扩展一个节点。
// 执行 right-left 轮即可覆盖闭区间，区间外链接保持不变。
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、right 与链长。
- 重连的三步顺序不能交换：先摘 next，再接到区间头，最后更新前驱。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
Q092_ReverseListII.java