这是leetcode里的第25道题。
题目要求:
给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表:
1->2->3->4->5
当 k = 2 时,应当返回:
2->1->4->3->5
当 k = 3 时,应当返回:
3->2->1->4->5
说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
设计思路:
使用分治法(应该可以这样说吧),不是要k个一组吗?那就把k个节点当做一小块,然后对这一小块进行倒置。然后再连接,难就是难在连接上。如下图(灵魂画师上线了!):
如图所示,r节点就是连接处,而且此时r节点指向的是null,当一组交换完后,p节点指向的也是null,而且p节点是这一组的最后一个节点。我们要做的就是把上一组完成的尾巴r节点连接上这一组交换完后的tail节点上。这就是关键之处。当然不能忘了,当到了最后一组不满足等于k时,要记得直接返回。
解题代码:
/** * definition for singly-linked list. * struct listnode { * int val; * listnode *next; * listnode(int x) : val(x), next(null) {} * }; */ class solution { public: listnode* reverse(listnode *head,listnode *tail){ if(head==tail)return head; listnode *p=head,*r=tail; stack<listnode*>sl; while(p!=r){ sl.push(p); p=p->next; } while(!sl.empty()){ r->next=sl.top(); sl.pop(); r=r->next; } r->next=null; return p; } listnode* reversekgroup(listnode* head, int k) { listnode *phead,*ptail,*res=null,*p,*r=null; int i=1; phead=ptail=head; while(ptail!=null){ if(i==k){ p=ptail->next; if(res==null)res=reverse(phead,ptail); else r->next=reverse(phead,ptail); r=phead; phead=ptail=p; i=1;continue; } ptail=ptail->next; i++; } if(i!=1){ if(r==null)return head; r->next=phead; } return res; } };
最后结果:
个人总结:
这道题难度是有的,也可以同过递归来缩短代码的长度。也可以在倒置之前先统计出长度,计算出需要倒置的次数,再保存起来。最后连接。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606113.html