题目
- K 个一组翻转链表
给你链表的头节点 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]
解题
方法一:递归
class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { if(!head) return nullptr; ListNode* tmp=head; bool reverseFlag=true; for(int i=0;i<k;i++){//如果剩余长度大于等于k,那么就反转,否则就不反转 if(!tmp) reverseFlag=false; else tmp=tmp->next; } ListNode* newhead; if(reverseFlag){//反转k个 newhead=reverseG(head,k); head->next=reverseKGroup(tmp,k);//反转之后k个(递归) } else newhead=head;//不反转 return newhead; } //反转链表 ListNode* reverseG(ListNode* head,int k){ ListNode* pre=nullptr; ListNode* cur=head; while(cur&&k-->0){ ListNode* tmp=cur->next; cur->next=pre; pre=cur; cur=tmp; } return pre; } };