92. 反转链表 II
题目描述
输入单链表头节点 head 和两个整数 left、right，满足 left <= right。链表用数组表示，例如 [1,2,3]。
节点位置从 1 开始计。把第 left 个到第 right 个节点这一段的顺序颠倒过来，其余节点不动。
返回处理后链表的头节点。
示例 1
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
解释：第 2 到第 4 个节点 2,3,4 颠倒为 4,3,2。
示例 2
输入：head = [5], left = 1, right = 1 输出：[5]
解释：只有一个节点，反转后不变。
数据范围
- 节点数为
n。 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
进阶：能否只遍历一遍链表就完成？
解题思路
加哑节点 dummy，让 pre 走 left-1 步停在反转段的前一个节点，cur = pre.next 是反转段的原第一个节点。之后做 right-left 次“头插”：把 cur 后面的节点 nxt 摘下来，插到 pre 的后面。cur 始终不动，慢慢被推到反转段的末尾。
为什么正确
第 t 次头插后，pre 后面的 t+1 个节点是原段前 t+1 个节点的逆序，且 cur 是其中最后一个。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
left = 1 时头节点会变，所以要返回 dummy.next 而不是 head。头插的四步顺序不能乱：先让 cur 跳过 nxt，再让 nxt 指向 pre.next，最后 pre.next = nxt。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
pre = dummy
for _ in range(left - 1):
pre = pre.next
cur = pre.next
for _ in range(right - left):
nxt = cur.next
cur.next = nxt.next
nxt.next = pre.next
pre.next = nxt
return dummy.nextclass Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
for (int i = 0; i < right - left; i++) {
ListNode nxt = cur.next;
cur.next = nxt.next;
nxt.next = pre.next;
pre.next = nxt;
}
return dummy.next;
}
}class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0, head);
ListNode* pre = &dummy;
for (int i = 0; i < left - 1; i++) {
pre = pre->next;
}
ListNode* cur = pre->next;
for (int i = 0; i < right - left; i++) {
ListNode* nxt = cur->next;
cur->next = nxt->next;
nxt->next = pre->next;
pre->next = nxt;
}
return dummy.next;
}
};func reverseBetween(head *ListNode, left int, right int) *ListNode {
dummy := &ListNode{0, head}
pre := dummy
for i := 0; i < left-1; i++ {
pre = pre.Next
}
cur := pre.Next
for i := 0; i < right-left; i++ {
nxt := cur.Next
cur.Next = nxt.Next
nxt.Next = pre.Next
pre.Next = nxt
}
return dummy.Next
}var reverseBetween = function(head, left, right) {
const dummy = new ListNode(0, head);
let pre = dummy;
for (let i = 0; i < left - 1; i++) {
pre = pre.next;
}
const cur = pre.next;
for (let i = 0; i < right - left; i++) {
const nxt = cur.next;
cur.next = nxt.next;
nxt.next = pre.next;
pre.next = nxt;
}
return dummy.next;
};function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
const dummy = new ListNode(0, head);
let pre: ListNode = dummy;
for (let i = 0; i < left - 1; i++) {
pre = pre.next!;
}
const cur = pre.next!;
for (let i = 0; i < right - left; i++) {
const nxt = cur.next!;
cur.next = nxt.next;
nxt.next = pre.next;
pre.next = nxt;
}
return dummy.next;
}