力扣题目解析--K个一组翻转链表
题目
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]
提示：
- 链表中的节点数目为
n 1 <= k <= n <= 50000 <= Node.val <= 1000
代码展示
/**
* 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:
// 翻转一个子链表，并且返回新的头与尾
pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
ListNode* prev = tail->next;
ListNode* p = head;
while (prev != tail) {
ListNode* nex = p->next;
p->next = prev;
prev = p;
p = nex;
}
return {tail, head};
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* hair = new ListNode(0);
hair->next = head;
ListNode* pre = hair;
while (head) {
ListNode* tail = pre;
// 查看剩余部分长度是否大于等于 k
for (int i = 0; i < k; ++i) {
tail = tail->next;
if (!tail) {
return hair->next;
}
}
ListNode* nex = tail->next;
// 这里是 C++17 的写法，也可以写成
// pair<ListNode*, ListNode*> result = myReverse(head, tail);
// head = result.first;
// tail = result.second;
tie(head, tail) = myReverse(head, tail);
// 把子链表重新接回原链表
pre->next = head;
tail->next = nex;
pre = tail;
head = tail->next;
}
return hair->next;
}
};逐行解析
函数 myReverse
pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail)：定义了一个函数，用于反转从head到tail的子链表，并返回反转后的新头和新尾。ListNode* prev = tail->next;：初始化prev指针为tail节点之后的节点。这是因为在反转过程中，最后一个节点（即原来的tail）需要指向它原本的下一个节点。ListNode* p = head;：初始化p指针为head，即要开始反转的第一个节点。while (prev != tail)：循环直到prev和tail相遇，意味着我们已经反转了整个子链表。ListNode* nex = p->next;：保存当前节点p的下一个节点，以防在改变p->next后丢失链表的其余部分。p->next = prev;：将当前节点p的next指向prev，完成反转。prev = p;：更新prev指针到当前节点p。p = nex;：移动p指针到下一个要处理的节点。
return {tail, head};：返回反转后的子链表的新头部（原来的tail）和新尾部（原来的head）。
函数 reverseKGroup
ListNode* hair = new ListNode(0);：创建一个新的哑节点（dummy node），它的next指向链表的原始头节点。这简化了边界条件的处理。hair->next = head;：让哑节点的next指向链表的头节点。ListNode* pre = hair;：初始化pre指针指向哑节点，pre用来追踪每个反转子链表前的一个节点。while (head)：当head不为空时，进入循环，尝试反转接下来的k个节点。ListNode* tail = pre;：设置tail指针为pre，准备寻找接下来的k个节点的末尾。for (int i = 0; i < k; ++i)：遍历接下来的k个节点，以确定是否有足够的节点来形成一个完整的反转组。tail = tail->next;：逐步移动tail指针到第k个节点。if (!tail)：如果在找到k个节点之前tail变成了nullptr，说明剩下的节点不足k个，直接返回结果链表。
ListNode* nex = tail->next;：保存tail节点之后的节点，作为下一次反转的起点。tie(head, tail) = myReverse(head, tail);：使用 C++17 的结构化绑定语法调用myReverse函数反转子链表，并同时获取新的头和尾指针。等价于：pair<ListNode*, ListNode*> result = myReverse(head, tail); head = result.first; tail = result.second;pre->next = head;：将pre的next设置为反转后的子链表的新头，连接上一部分链表。tail->next = nex;：将反转后的子链表的新尾的next设置为nex，即下一组要反转的节点。pre = tail;：更新pre指针到当前反转组的尾部，为下一次反转做准备。head = tail->next;：更新head指针到下一组要反转的节点。
return hair->next;：最后返回哑节点的next，即反转后的链表的真正头节点。