给你链表的头节点 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]
刷过leetcode的hot100，应该对这个题都有思路，但是链表的这个题它为什么能算hard，还是因为大家写的通过率不高，思路看着不难，但其实里面很多细节，自己手写起来会有很多问题，那我们来捋清一下思路。
首先，链表翻转在看完前面的分享，三指针应该很快可以写出来，那么现在让我们实现k个一组的链表翻转，最简单的思路：
- 判断后面还有没有k个node
- 如果有，翻转
- 如果没有，返回那个地方的头节点
-
做链表的题目，首先别怕多创建指针，用就完事了，实现翻转，tail尾部用一个指针存放他的下一个next，head头节点也用一个指针指向，然后在翻转过程中需要一个指针用于迭代。剩下的就是画个图模拟局部的情况，迭代，考虑边界问题，后面代码会有详细注释。
在到后面就是判段一下后面是否还有k个节点，然后把翻转后的链表拼接起来。（另外如果能够完整无误的写出这样的代码，那证明基本功已经很好了，加油）
class Solution { public: // 定义一个函数用于翻转链表中指定区间的节点 pair<ListNode*, ListNode*> myreverse(ListNode* head, ListNode* tail) { ListNode* pre = tail->next; // 保存区间翻转前的前驱节点 ListNode* p = head; // 当前节点从头部开始 // 进行区间翻转 while (pre != tail) { ListNode* nex = p->next; // 保存下一个节点 p->next = pre; // 当前节点指向前驱节点，实现翻转 pre = p; // 更新前驱节点为当前节点 p = nex; // 当前节点移向下一个节点 } return { tail, head }; // 返回翻转后的头节点和尾节点 } ListNode* reverseKGroup(ListNode* head, int k) { ListNode* hair = new ListNode(0); // 创建一个虚拟头节点，指向链表头部 hair->next = head; // 虚拟头节点的下一个节点为链表头部 ListNode* pre = hair; // pre指针指向当前处理的区间的前驱节点 while (head) { ListNode* tail = pre; // tail指针指向当前处理的区间的尾节点 // 找到当前区间的尾节点 for (int i = 0; i < k; i++) { tail = tail->next; if (!tail) // 如果区间长度不足k，直接返回虚拟头节点的下一个节点 return hair->next; } ListNode* nex = tail->next; // 保存当前区间的下一个节点 tie(head, tail) = myreverse(head, tail); // 调用翻转函数，返回翻转后的头节点和尾节点 pre->next = head; // 前驱节点指向翻转后的头节点 tail->next = nex; // 翻转后的尾节点指向下一个节点 pre = tail; // 更新前驱节点为翻转后的尾节点 head = tail->next; // 当前处理的头节点更新为翻转后的尾节点的下一个节点 } return hair->next; // 返回虚拟头节点的下一个节点作为翻转后的链表头部 } };
另外有一种递归的写法，代码会更加简介，且空间复杂度为O(1)；
具体思路：思路和模拟方法相同，首先判断链表是否有K个数，不足则直接返回head。否则对前K个数进行反转，然后进行递归处理。
class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode *p = head; for(int i = 0; i < k; i++) { if(!p) return head; // 如果剩余节点数量不足k个，则不进行翻转，直接返回头节点 p = p->next; // 指针p向后移动k个位置 } ListNode *q = head; // 指针q指向当前待翻转的区间的头节点 ListNode *pre = nullptr; // pre指向翻转后的区间的尾节点 while(q != p) { // 循环翻转整个区间内的节点 ListNode *tmp = q->next; // 保存q的下一个节点 q->next = pre; // 将q的next指针指向其前驱节点pre，实现翻转 pre = q; // 更新pre为当前翻转后的节点 q = tmp; // 更新q为下一个待翻转的节点 } head->next = reverseKGroup(p, k); // 将翻转后的区间与后面的链表连接起来 return pre; // 返回翻转后的区间的头节点作为新的头部 } };
