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

整体大思路把链表按 k 个节点分成一组一组对每一组单独翻转然后把翻转后的组和前后的组重新连接起来最后不足 k 个的组不翻转。我们只需要解决 3 个小问题怎么判断剩下的节点够不够 k 个怎么翻转一组 k 个节点怎么把翻转后的组和前后的组连接起来步骤 1判断剩余节点是否够 k 个我们用一个tail指针从当前组的前驱节点pre开始往前走 k 步如果能走完 k 步说明剩余节点够 k 个可以翻转如果走不到 k 步就到nullptr了说明不够直接结束步骤 2翻转一组 k 个节点这是 206 题「反转链表」的变种我们需要翻转从head到tail的子链表并且返回翻转后的新头和新尾方便后面连接。步骤 3把翻转后的组重新连接起来这是这道题最关键的一步翻转前一定要先保存下一组的头节点不然会断链固定 4 步连接逻辑保存下一组的头ListNode* nex tail-next;翻转当前组得到新头和新尾tie(newHead, newTail) reverse(head, tail);上一组的尾指向新头pre-next newHead;新尾指向下一组的头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 pairListNode*,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; ik;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; } };