题目
给你链表的头节点 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
进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
解答
编写一个函数，用于实现反转链表的核心逻辑，思路如下：
初始化一个前驱节点prev和一个当前节点curr，分别指向空和头节点。
循环k次，每次做以下操作：
保存当前节点的下一个节点next，以免丢失。
将当前节点的next指针指向前驱节点prev，实现反转。
将前驱节点prev更新为当前节点curr，为下一次反转做准备。
将当前节点curr更新为下一个节点next，继续遍历链表。
这样就可以将链表中的k个节点反转，并返回反转后的头尾指针。
对以上函数进行一个图示说明：
假设链表为1->2->3->4->5，k为3，那么反转后的链表应该为3->2->1->4->5。
初始状态：
prev: null curr: 1 next: 2 null <- prev curr -> next -> 3 -> 4 -> 5第一次循环：
prev: 1 curr: 2 next: 3 null <- prev <- curr next -> 4 -> 5第二次循环：
prev: 2 curr: 3 next: 4 null <- prev <- curr next -> 5第三次循环：
prev: 3 curr: 4 next: 5 null <- prev <- curr next结束循环，返回{prev, head}即{3,1}。
prev head | | v v null<-3<-2<-1 4->5
代码的整体思路是：
- 定义一个虚拟头节点dummy，指向原链表的头节点head，这样可以方便处理边界情况。
- 定义一个前驱节点prev，初始指向dummy，用来连接反转后的链表段。
- 用一个while循环遍历整个链表，每次循环做以下操作：
- 定义一个尾部指针tail，初始指向头部指针head，并向后移动k-1次，如果为空则说明剩余长度不足k，直接返回dummy->next即可。
- 保存下一段链表的头部指针nextHead，并断开与当前段的连接。
- 调用反转函数reverseList，输入当前段的头部指针head和长度k，返回反转后的新头部和新尾部，并将其连接到前驱和下一段上。
- 更新前驱为新尾部，更新头部为下一段头部。
这样就可以将整个链表按照每k个节点进行反转，并返回dummy->next作为新链表的头节点。
代码的时间复杂度是O(n)，因为我们只需要遍历一次链表，每个节点最多被访问两次。 代码的空间复杂度是O(1)，因为我们只使用了常数个额外变量，没有使用递归或栈。C++代码实现如下：
/**
* 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:
// 定义反转链表的函数，输入一个链表头节点和一个长度k，返回反转后的头节点和尾节点
pair<ListNode*, ListNode*> reverseList(ListNode* head, int k) {
// 初始化前驱节点和当前节点
ListNode* prev = nullptr;
ListNode* curr = head;
// 遍历k次，每次将当前节点指向前驱节点，并更新前驱和当前节点
for (int i = 0; i < k; i++) {
ListNode* next = curr->next; // 保存下一个节点
curr->next = prev; // 反转指针
prev = curr; // 更新前驱
curr = next; // 更新当前
}
// 返回反转后的头节点和尾节点，即原来的尾节点和头节点
return {prev, head};
}
// 定义leetcode 25的主函数，输入一个链表头节点和一个整数k，返回反转后的链表头节点
ListNode* reverseKGroup(ListNode* head, int k) {
// 初始化虚拟头节点和前驱节点
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* prev = dummy;
while (head != nullptr) { // 遍历链表直到为空
// 初始化尾部指针为头部指针，并向后移动k-1次，如果为空则说明剩余长度不足k，直接返回虚拟头节点的下一个即可
ListNode* tail = head;
for (int i = 0; i < k - 1; i++) {
tail = tail->next;
if (tail == nullptr) return dummy->next;
}
// 保存下一段链表的头部指针，并断开与当前段的连接
ListNode* nextHead = tail->next;
tail->next = nullptr;
// 调用反转函数，得到反转后的新头部和新尾部，并将其连接到前驱和下一段上
auto reversedPair = reverseList(head, k);
prev->next = reversedPair.first;
reversedPair.second->next = nextHead;
// 更新前驱为新尾部，更新头部为下一段头部
prev = reversedPair.second;
head = nextHead;
}
return dummy->next;
}
};