反转链表 II
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你单链表的头指针 head 和两个整数 left 和 right，其中 left <= right。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。
位置从 1 开始计数。例如 left=2, right=4 表示反转第 2、3、4 号节点。
示例 1
反转第 2～4 号节点（2→3→4 变为 4→3→2），第 1、5 号节点不动。
示例 2
模拟答题者思考
1. 暴力：把 [left, right] 区间节点值取出来，反转后再填回去——可行但多用了数组，且要额外处理指针。
2. 重复劳动：若先整体反转再反转两侧，要三次反转，边界 left=1 时前驱不好找。
3. 优化：设 prev 为第 left-1 个节点；在 [left, right] 内用头插法——反复把 cur 的下一个节点拔下来，插到 prev 后面。执行 right-left 次后，区间恰好反转，且 prev 仍连着区间外的前段。
4. 与「全链表反转」对比：全反转时 cur 不断前移；这里 cur 钉在左端点，只动它后面的节点，前段链表不用重新遍历拼接。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dummy | ListNode* | 定义：哨兵节点，dummy.next = head维护：始终挂在链表最前，方便 left=1 时仍有「前驱」更新：创建后不再改，最后返回 dummy.next |
prev | ListNode* | 定义：待反转区间 左侧紧邻的前驱（第 left-1 号节点）维护：头插法中，每次被拔出的节点都插到 prev.next 之后更新：先走 left-1 步定位；反转循环内 prev 不动，只改 prev.next |
cur | ListNode* | 定义：原区间起点（第 left 号节点），反转后将成为区间尾维护：整个头插过程中 cur 指针不移动，始终指向「将要变成尾巴」的那个节点更新：定位后固定；每轮把 cur.next 拔出来头插，cur 仍指向同一节点 |
nxt | ListNode* | 定义：每轮从 cur 后面拔出的节点（cur.next）维护：被头插到 prev 之后，成为新区间头更新：每轮 nxt = cur.next，改链后 nxt 接到 prev.next 位置 |
落码步骤
1. dummy = ListNode(0, head)，prev = dummy
2. prev 向前走 left - 1 步，停在区间左边界的前驱
3. cur = prev.next（区间第一个节点，反转后变尾）
4. 循环 right - left 次头插：nxt = cur.next → cur.next = nxt.next → nxt.next = prev.next → prev.next = nxt
5. 返回 dummy.next
代码实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
prev = dummy
for _ in range(left - 1):
prev = prev.next
cur = prev.next # 区间左端点，头插后成为区间尾
for _ in range(right - left):
nxt = cur.next # 待头插的节点
cur.next = nxt.next # 从 cur 后摘下 nxt
nxt.next = prev.next # nxt 指向当前区间头
prev.next = nxt # nxt 成为新区间头
return dummy.nextclass Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0, head);
ListNode* prev = &dummy;
for (int i = 0; i < left - 1; ++i) {
prev = prev->next;
}
ListNode* cur = prev->next; // 区间左端点，头插后成为区间尾
for (int i = 0; i < right - left; ++i) {
ListNode* nxt = cur->next;
cur->next = nxt->next;
nxt->next = prev->next;
prev->next = nxt;
}
return dummy.next;
}
};
// 时间 O(n)，空间 O(1)
// 也可用：先找区间首尾，区间内标准三指针反转，再拼接前后段复杂度分析
O(n)
O(1)
常见坑
头插循环次数是 right - left 而不是 right - left + 1：cur 本身已在区间内，只需把后面 right-left 个节点依次拔到前面。
头插四步顺序不能乱：必须先 cur.next = nxt.next 再改 nxt.next，否则可能断链或成环。
left=1 时若没有 dummy，prev 无处安放；用哨兵后统一处理。
必测边界 Case
head=[5], left=1, right=1 → [5]（循环 0 次）
head=[1,2,3], left=1, right=3 → [3,2,1]
head=[1,2,3,4,5], left=4, right=5 → [1,2,5,4,3] 中后段 [4,5]→[5,4]