Leetcode算法面试题 k个一组翻转链表

首先看一下题目描述:

给出一个链表,每k个节点一组进行翻转,并返回翻转后的链表。k是一个正整数,它的值小于或等于链表的长度。如果节点总数不是k的整数倍,那么将最后剩余节点保持原有顺序。示例:给定这个链表:1->2->3->4->5当k=2时,应当返回:2->1->4->3->5当k=3时,应当返回:3->2->1->4->5说明:你的算法只能使用常数的额外空间。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

再来看一下输入输出的要求:

/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(intx){val=x;}*}*/classSolution{publicListNodereverseKGroup(ListNodehead,intk){}}

注意到的关键点:
1.常数的额外空间,不是说只能使用基本类型的额外空间,而是让你用尽量少的对象空间
2.一定要做结点交换,其实就是重新安排指针。
3.给出的是个单向链表,所以在设计递进单元,指针重定向的时候,要注意指针位置的保存。不然可能会丢掉指针导致递进失败。(这个问题在大四刷数据结构题的时候吃了不少亏。)
递进单元设计
先不考虑其他干扰因素,只考虑对长度为k的链表的反转问题。我想到的是两种方法:
第一种,头插法。其思想见图。

这种方法,相当于建立另外一个链表–L的头,然后,将要处理的列表递进处理,一个一个的插入新链表,最后返回新L.next即可。
然后再考虑一下多个这样的处理单元(n个结点,k个为一个单元)合并的事情,每次处理完这样一个单元后,要拿到两个结点才可以进行合并,第一就是L,这个是本来就有的,通过L.next可以获取到单元链表的头,第二就是最后一个结点,其实最后一个结点就是最开始插入的那个结点,所以每次处理的时候,要把它保存一下。
第二种,直接指针反转。

因为是单链表,为了防止指针结点丢失,我们至少需要三个指针来进行操作,以及递进。首先红色的指针代表当前结点,绿色的代表上个结点,蓝色的代表下一个结点,那么在每个操作单元要做的事情就是:

next=cur.next;//首先获取到递进的下一项防止结点丢失cur.next=prev;//处理当前结点的指针,它本来应该指向下一个的,现在让它指向前一个prev=cur;//前进cur=next;//注意这里,不是cur=cur.next,因为cur的next已经重新指向前一位了,它的下一位已经丢失,所以第一步先把它的下一位用next保存下来了

当cur处理完最后一个结点的时候(第k个),prev指向最后一个结点,next指向下一个结点。
进行链表拼接的时候,也需要两个结点,首先头结点就是prev,而尾结点同样是处理的第一个结点,那么也需要记录一下第一个结点。

码代码
第一种思想的实现:

/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(intx){val=x;}*}*/classSolution{publicListNodereverseKGroup(ListNodehead,intk){ListNodelist=newListNode(0);//永远表示头插法要插入的头结点ListNodereturn_list=list;//最终要返回的链表头ListNodeStart=newListNode(0);//每次处理反转时,开始的位置ListNodeEnd=newListNode(0);//每次处理反转时,结束的位置intcount=0;//计数while(head!=null){//对要处理的链表按k个一组递进处理count=0;Start=head;End=Start;//开始结束指针的初始化while(End!=null&&count<k){End=End.next;count++;}//首先判定一下当前组是否有k个if(count==k){//有k个则进行处理list.next=head;//因为遇到list.next=null的问题,好像不能tmp=list.next这样去赋值,所以就手动给它先加一个结点head=head.next;//手动递进一位for(inti=1;i<k;i++){//因为已经加了一个结点,所以i从1开始,ListNodetmp=list.next;list.next=head;head=head.next;list.next.next=tmp;//头插法}Start.next=null;//在这里必须清空头数字的指针,使其变成真正的尾部list=Start;//Start里保存的就是尾部,而list要永远是头插法要插入的头,所以要让list定位到Start开始下一轮处理,这里可以这么理解,list一次往后跳k个结点,每次处理完之后,都跳到链表的最后,以便下一轮在其后面插入结点}else{//如果不足k个,直接链接即可list.next=Start;break;}}returnreturn_list.next;//因为list是往后跳的,但是return_list是保存着list的最开始的位置的,所以返回的时候要返回return_list;}}

第二种的实现:
PS:参考了评论区的递归的思想。

/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(intx){val=x;}*}*/classSolution{publicListNodereverseKGroup(ListNodehead,intk){ListNodeprev=null;ListNodecur=head;ListNodeS=head;//和前一个思想一样,先用它递进看一下是不是有k个结点ListNodenext=null;intcount=0;inti=0;while(S!=null&&count<k){S=S.next;count++;}if(count==k){while(i<k&&cur!=null){//递归的末端1next=cur.next;cur.next=prev;prev=cur;cur=next;i++;//这里学会了用prev来保存前一变量,}if(next!=null){//递归的传递端head.next=reverseKGroup(next,k);//在这里优化成了递归}returnprev;//最终返回}else{returnhead;//递归的末端2}}}

复杂度总结:
首先可以看到关键处理过程是一遍扫描,之前又有一次预扫描,所以时间复杂度应该是O(2n)。
最后
点击提交,看下成绩~

评论区
Rick ©2018