给你链表的头节点 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) 额外内存空间的算法解决此问题吗？
解题思路：模拟
这道题看似是困难题，但其实没什么技巧，就是模拟题，只不过需要有几个步骤罢了！
首先，既然是 k 个为一组，那么我们肯定就得求出一共需要逆序多少组，所以一开始就得遍历链表求出一共有多少节点，假设有 n 个节点，那么一共就有 n / k 组需要逆序，并且如果最后一组不完整的话，其实不会算入这 n / k 组中的！
接着我们就可以使用多种方式来对每组节点进行逆序了，比如说使用栈，当栈中节点没有达到 k 个的时候就不进行操作，达到了就拿出来，直接达到逆序效果，但是就不满足这道题的进阶要求：O(1) 的额外空间。所以我们换个思路！
其实很简单，就是使用我们前面说到的头插法，屡试不爽！以题目给的第一个例子为例，如下图所示：
但是问题来了，因为一组逆序完之后，新的头节点就不能是 newhead 了，不然的话头插进来就整体逆序了，我们要的是一组一组逆序的。我们可以发现新的头节点位置，其实就是新的一组中的第一个节点，比如上面的 1、2 是一组，它们逆序之后是 2、1，那么此时 1 其实就是下一组 3、4 的要作为头插法的节点！
所以我们每次逆序一个组的时候，要先记录下其第一个逆序的节点，作为下一组进行头插法的新头节点！如下图所示：
然后最后别忘了还有最后一组不完整的也要链接上！
/**
* 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) {
// 1. 先找出一共有多少个节点
int n = 0;
ListNode* cur = head;
while(cur != nullptr)
{
n++;
cur = cur->next;
}
// 2. 计算出一共需要逆序多少组
int groups = n / k;
// 3. 对这几组进行逆序，这里使用头插法
ListNode* newhead = new ListNode();
ListNode* prev = newhead;
cur = head;
while(groups--)
{
ListNode* tmp = cur;
for(int i = 1; i <= k; ++i)
{
// 头插法进行逆序插入
ListNode* next = cur->next; // 先记录下一个节点防止丢失
cur->next = prev->next;
prev->next = cur;
cur = next;
}
prev = tmp; // 让prev跳到下一组的新头节点
}
prev->next = cur; // 别忘了还有最后一组不完整的
// 4. 释放新头节点并且返回
prev = newhead->next;
delete newhead;
return prev;
}
};