2021/04/25
寻找待操作结点的「前一个」结点，这种问题，要考虑到如果要找的结点是 head 的前一个结点怎么办，因此引入哨兵头结点往往可以简化代码。
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode sentry = new ListNode(0);
sentry.next = head;
// 寻找前驱结点
int m = 1;
ListNode prev = sentry;
while (m < left) {
m += 1;
prev = prev.next;
}
// 反转单链表
ListNode start = prev.next;
ListNode oldHead = start;
ListNode collector = null;
int n = 0;
while (n < right - left + 1) {
n++;
ListNode t = start.next;
start.next = collector;
collector = start;
start = t;
}
prev.next.next = prev.next;
// 前驱结点接上
prev.next = collector;
// 后驱结点接上
oldHead.next = start;
return sentry.next;
}
}
也可以减少一个 oldHead 的局部变量，因为 prev.next 一直是指向这个变量的。
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode sentry = new ListNode(0);
sentry.next = head;
// 寻找前驱结点
int m = 1;
ListNode prev = sentry;
while (m < left) {
m += 1;
prev = prev.next;
}
// 反转单链表
ListNode start = prev.next;
ListNode collector = null;
int n = 0;
while (n < right - left + 1) {
n++;
ListNode t = start.next;
start.next = collector;
collector = start;
start = t;
}
// 反转链表的尾结点接上
prev.next.next = start;
// 粉转链表的头结点接上
prev.next = collector;
return sentry.next;
}
}