LeetCode 92. 反转链表 II
题目描述
题意分析
只反转单链表中第
left个到第right个节点，区间两端都包含在内，区间外的节点顺序保持不变。位置从1开始，题目保证left、right都在链表范围内且left <= right。要修改的是节点的连接方向。反转结束后，不仅区间内部顺序要正确，前面的链表也要接到新的区间头部，新的区间尾部还要接回后面的链表。当
left = 1时，整条链表的头节点会变化；当left = right时，不需要修改。
解法：头插法局部反转
核心思路
[!blue]
反转一个区间，可以逐个把后面的节点移到区间最前面。先找到区间前驱
pre，使pre.next始终表示当前区间的头；再用cur固定指向原来的区间首节点。这个节点最终会成为区间尾部，整个过程中不需要移动cur本身。开始时，把只有
cur的这一段视为已经反转好的部分，cur.next指向尚未处理的下一个节点。每轮取出next = cur.next，将它从原位置摘下，再放到pre后面。新加入的节点出现在已反转部分的最前面，之前反转好的顺序保持不变，因此已反转部分的长度增加一。具体连接分三步完成：
cur.next = next.next先跳过待移动节点，保住剩余链表；next.next = pre.next让它接到当前区间头部；最后pre.next = next将区间入口更新为这个节点。修改期间既保存了待移动节点，也始终保留了未处理部分的入口，不会丢失链表。
pre一直留在区间外，cur一直是已反转部分的尾节点；每轮变化的是它们的next。当全部移动完成，pre.next已经指向新头，cur.next正好指向原第right个节点之后的部分，所以两端无需再单独拼接。区间共有
right - left + 1个节点，第一个节点已经作为初始的已处理部分，只需移动后面的right - left个节点。使用指向原头的哨兵dummy后，即使left = 1，也可以把dummy当作pre，用完全相同的操作更新新的链表头。
解题步骤
- 创建哨兵节点
dummy，令dummy.next = head，从它开始寻找区间前驱。- 向后走
left - 1步，使pre停在反转区间之前。- 令
cur = pre.next，固定指向原区间首节点。- 重复
right - left次：保存next = cur.next，再依次修改cur.next、next.next、pre.next，把这个节点插到区间最前面。- 返回
dummy.next。若left = right，第四步执行零次，原链表保持不变。
代码实现
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++) {
// pre 与 cur 保持不动，原首节点 cur 将成为段尾，每次摘下它的后继。
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++ {
// pre 与 cur 保持不动，原首节点 cur 将成为段尾，每次摘下它的后继。
next := cur.Next
// 先从原位置摘除，再插到反转区间最前面。
cur.Next = next.Next
next.Next = pre.Next
pre.Next = next
}
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(n)$，先移动
left - 1步寻找前驱，再做right - left次常数操作，总次数不超过链表长度的量级。- 空间复杂度：$O(1)$，只使用一个哨兵节点和固定数量的指针。
关键点总结
[!green]
- 哨兵节点消除反转区间从链表头开始的特殊处理。
pre和cur始终不动，每轮只搬动cur.next。- 循环次数是
right - left；当left = right时自然执行 0 次。
易错点总结
[!yellow]
pre应停在第left - 1个节点，不能多走一步。- 修改
cur.next前必须先保存待移动节点。- 头插顺序应为
cur.next = next.next、next.next = pre.next、pre.next = next。- 必须返回
dummy.next，否则left = 1时会返回旧头节点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 206. 反转链表 | 简单 | 复用原地反转指针，额外保存区间前驱与反转后的尾部连接。 |
| 25. K 个一组翻转链表 | 困难 | 把局部反转扩展到每个k节点分组，原题重复应用反转子过程。 |
| 143. 重排链表 | 中等 | 拆分链表后反转并重新连接；本题只反转指定区间，该题从中点拆分并交替合并首尾。 |
| 234. 回文链表 | 简单 | 拆分链表后反转并重新连接；本题只反转指定区间，该题反转后半段后比较对称值。 |