力扣HOT100（31）K 个一组翻转链表

整体大思路：

把链表按 k 个节点分成一组一组，对每一组单独翻转，然后把翻转后的组和前后的组重新连接起来，最后不足 k 个的组不翻转。

我们只需要解决 3 个小问题：

1. 怎么判断剩下的节点够不够 k 个？
2. 怎么翻转一组 k 个节点？
3. 怎么把翻转后的组和前后的组连接起来？

步骤 1：判断剩余节点是否够 k 个

我们用一个tail指针，从当前组的前驱节点pre开始，往前走 k 步：

• 如果能走完 k 步，说明剩余节点够 k 个，可以翻转
• 如果走不到 k 步就到nullptr了，说明不够，直接结束

步骤 2：翻转一组 k 个节点

这是 206 题「反转链表」的变种，我们需要翻转从head到tail的子链表，并且返回翻转后的新头和新尾，方便后面连接。

步骤 3：把翻转后的组重新连接起来

这是这道题最关键的一步，翻转前一定要先保存下一组的头节点，不然会断链！

固定 4 步连接逻辑：

1. 保存下一组的头：ListNode* nex = tail->next;
2. 翻转当前组，得到新头和新尾：tie(newHead, newTail) = reverse(head, tail);
3. 上一组的尾指向新头：pre->next = newHead;
4. 新尾指向下一组的头：newTail->next = nex;

然后更新指针，准备处理下一组：

• pre = newTail;（下一组的前驱是当前组的新尾）
• head = nex;（下一组的头是之前保存的 nex）

• /** * 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类型的 函数 翻转一个子链表，并返回新的头和尾 //pair容器用于存放成对出现的 可以返回新生成的pair.first pair.second pair<ListNode*,ListNode*> myReverse(ListNode* head,ListNode* tail){ ListNode* prev = tail->next; ListNode* p = head; while(prev != tail){ //反转链表 ListNode* nex = p->next;//p的下一个存在nex中 p->next = prev; prev = p; p = nex; } return {tail,head};//返回新的头 和尾巴 } ListNode* reverseKGroup(ListNode* head, int k) { ListNode* hair = new ListNode (-1,head); ListNode* pre = hair; while(head){ ListNode* tail = pre;//尾指针 用来判断剩余部分还有k个吗。初始在虚拟头 for(int i = 0; i<k;i++){ tail = tail->next;//tail一直往前走 if(tail == nullptr){//走到空说明不满足k步了 直接返回 终止循环 return hair->next; } } //现在就是满足k步的 ListNode * nex = tail->next;//tail现在的位置在第k个元素 //接下来调用函数 进行翻转 tie(head, tail) = myReverse(head, tail); //子链表重新接回去 pre->next = head; tail->next = nex; pre = tail;//用来存放下一组头的前驱 head = tail->next;//开始前移 } return hair->next; } };