概述
起因：leetcode题目 25. K 个一组翻转链表
问题描述
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例一：
输入：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]
解决方法
我们需要构建一个函数，它会对链表进行K个节点翻转。而不断使用这个函数，就可以对每K个节点进行翻转。
点击查看代码
struct Res{ListNode *head;bool flag;ListNode *tail;};Res reverse(ListNode* head,int k){ListNode newHead;ListNode *subHead,*subTail,*cur,*temp;//subHead 记录反转过程的头节点//subTail 记录反转过程的尾节点//cur 要反转的节点//temp 用于反转的中间变量int cnt = 0; //记录长度if(head){subHead = head;subTail = head;cur = head->next;cnt++;}while(cur && cnt<k){temp = cur;cur = cur->next;subTail->next = temp->next;temp->next = subHead;subHead = temp;cnt++;}bool flag = true;if(cnt<k) flag = false;return {subHead,flag,subTail};}
函数逻辑
-
一开始翻转链表的
head和tail都是正常链表的头节点，cur则是要进行翻转的节点- 我们把
cur作为新的head，即旧的head会成为cur的下一个节点。 cnt进行自增加一
- 我们把
-
重复这个过程，直到
cur为空。 -
然后判断
cnt与K的关系：cnt<K的话，则未能反转K个节点。flag为 False。
注意：这个过程中
tail不需要变化，因为一开始的正常链表头节点就是翻转后的尾节点。
其中，函数返回翻转后的头节点和尾节点。特别地，flag是判断是否翻转了K个数。
实现不满足K个节点则不翻转
当不满足K个节点时，函数返回的 res 中的flag属性会为False。
这时对这个翻转后的链表再次进行翻转的话，就可以实现不翻转。
主函数实现
ListNode* reverseKGroup(ListNode* head, int k) {ListNode *newHead,*subTail;//首先进行一次翻转，并初始newHead和subTailauto res = reverse(head,k);newHead = res.head; subTail = res.tail;//如果第一次翻转就不满足K个节点，再次进行翻转，并返回新的newHeadif(res.flag == false){res = reverse(newHead,k);newHead = res.head;subTail = res.tail;return newHead;} //对每K个节点进行翻转while(1){auto res = reverse(subTail->next,k); //不满足K个节点，再次翻转，并直接返回结果。if(res.flag == false){res = reverse(res.head,k);return newHead;}// 对subTail进行更新：链接翻转后的子链表，并把subTail更新为子链表的tail。subTail->next = res.head;subTail = res.tail;cout<<subTail->val<<endl;}return newHead;
}
