上述的顺序不能错，不然会有问题。原因就在于p2.next = None，如果这个放在最后，那么我们的 cur 会提前断开。
while cur:
i += 1
if i == m - 1:
p1 = cur
next = cur.next
if m < i <= n:
cur.next = pre
if i == m:
p2 = cur
p2.next = None
if i == n:
p3 = cur
if i == n + 1:
p4 = cur
pre = cur
cur = next
关键点解析
四点法
链表的基本操作
考虑特殊情况 m 是 1 或者 n 是链表长度的情况，我们可以采用虚拟节点 dummy 简化操作
用四个变量记录特殊节点， 然后操作这四个节点使之按照一定方式连接即可。
注意更新 current 和 pre 的位置， 否则有可能出现溢出
代码
我把这个方法称为 四点法
语言支持：JS, Python3， CPP
JavaScript Code:
/*
* @lc app=leetcode id=92 lang=javascript
*
* [92] Reverse Linked List II
*
* https://leetcode.com/problems/reverse-linked-list-ii/description/
*/
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} m
* @param {number} n
* @return {ListNode}
*/
var reverseBetween = function (head, m, n) {
// 虚拟节点，简化操作
const dummyHead = {
next: head,
};
let cur = dummyHead.next; // 当前遍历的节点
let pre = cur; // 因为要反转，因此我们需要记住前一个节点
let index = 0; // 链表索引，用来判断是否是特殊位置（头尾位置）
// 上面提到的四个特殊节点
let p1 = (p2 = p3 = p4 = null);
while (cur) {
const next = cur.next;
index++;
// 对 (m - n) 范围内的节点进行反转
if (index > m && index <= n) {
cur.next = pre;
}
// 下面四个if都是边界, 用于更新四个特殊节点的值
if (index === m - 1) {
p1 = cur;
}
if (index === m) {
p2 = cur;
}
if (index === n) {
p3 = cur;
}
if (index === n + 1) {
p4 = cur;
}
pre = cur;
cur = next;
}
// 两个链表合并起来
(p1 || dummyHead).next = p3; // 特殊情况需要考虑
p2.next = p4;
return dummyHead.next;
};
Python Code:
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if not head.next or n == 1:
return head
dummy = ListNode()
dummy.next = head
pre = None
cur = head
i = 0
p1 = p2 = p3 = p4 = None
while cur:
i += 1
next = cur.next
if m < i <= n:
cur.next = pre
if i == m - 1:
p1 = cur
if i == m:
p2 = cur
if i == n:
p3 = cur
if i == n + 1:
p4 = cur
pre = cur
cur = next
if not p1:
dummy.next = p3
else:
p1.next = p3
p2.next = p4
return dummy.next
