注意：反转结束后，从原来的链表上看，\(pre\) 指向反转这一段的末尾，\(cur\) 指向反转这一段后续的下一个节点。
206.反转链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr, *curr = head;
while (curr) {
ListNode* nxt = curr->next;
curr->next = pre;
pre = curr;
curr = nxt;
}
return pre;
}
};
92.反转链表Ⅱ
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode *dummy = new ListNode(0, head), *p0 = dummy;//left 为 1 时没有上一个节点，因此要维护一个哨兵节点
for (int i = 0; i < left - 1; i++) p0 = p0->next;//结束时 p0 指向 left 的上一个节点
ListNode *pre = nullptr, *cur = p0->next;
for (int i = 0; i < right - left + 1; i++) {
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
p0->next->next = cur;
p0->next = pre;
return dummy->next;
}
};
25.K个一组翻转链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* cur = head;
int len = 0;
while (cur) {
len++;//计算链表长度
cur = cur->next;
}
ListNode *dummy = new ListNode(0, head), *p0 = dummy;
ListNode *pre = nullptr, *curr = head;
while (len >= k) {//剩余元素比 k 大就反转链表节
len -= k;
for (int i = 0; i < k; i++) {
ListNode *nxt = curr->next;
curr->next = pre;
pre = curr;
curr = nxt;
}
ListNode *nxt = p0->next;
p0->next->next = curr;
p0->next = pre;
p0 = nxt;
}
return dummy->next;
}
};