00:00
下面我们来完成单链表的一个反转,这是腾讯的一个面试题,好吧,我们来一起做一做,那么单链表的一个反转呢,相对来说麻烦一点,就是你。你不一定就是这个东西你不动脑筋是做不出来的,还是有一点难度啊,就说这个呢,有一点难度,虽然不是很大,但是呢有点难度。难度。好的。好的。难度啊难度,那现在呢,我们来把这一个单链表的反转的思路给同学们分析一把。你看我会准备怎么做啊,我会准备准备怎么做。啊,首先呢,我们把这个链表先拿过来。这个是我们的一个链表。他准备把这个链表进行一个反转。进行一个反转,怎么反转呢?来跟上我的思路哈。这是原始的链表,他希望比如说你这个数数组,它原来的编号是二,这个编号是五,这个编号是九。
01:09
他希望通过这个反转以后呢,这个链表就变成了这样子的。听我说啊,他希望通过一个反转以后,链表呢,变成了这个德行。变成什么样子了?变成这样子了?往这边移动一下这个。移动起来有点慢。好,我这样移动,那最后这个这个第一个数据就变成九了。就是这个节,它是把这个节点反转啊,就是相当于说把这个节点放到最前面了,不是简单把数据进行一个变化哈,呃,这变成了二。是不是相当于说把这个节点拿到最前面去了,中间因为你反转了,它还在中间吗?二呢,变成最后这一个节点。就这意思,就是这个就是所谓的。
02:00
这个就是我们所谓的一个反转。反转,那反转我们的思路应该是什么样子的呢?大家看我的思路。我的思路是这样子啊,但每个人啊,不一定我是这样想的,同学们,我画一个图,帮助大家理解。啊,我我先把这个写出来啊,就是干什么呢?呃,从头我先先去创建先去。呃,定义一个啊,定义一个新一个节点,定义一个节点,这个节点呢,比如说我取个名字叫做reverse。Re reverse reverse re reverse,反转的一个头。当然这个头呢,我初始化是一个新的hero node。OK,这是我要做的第一件事情,第二件事情干什么呢?就是从头到尾。
03:02
告为便利,原来的注意听啊,原注意听这句话啊,原来的这个链表。是不是原原原来表每遍历每立一个节点。干什么呢。就将其。哦,将其摘下。啊,摘一下就是取出来吧。呃,将其取出并放在。放在新的。新的这个链表的链表的最前端。最前端。OK,那么第三句话呢,最后我们把这个原先这个头节点害的就是原来的,注意听啊,是原来的这个链表的这个high的的next指向这个rivers。Rivers hide的点next就可以了,那所以说啊,从头到尾遍历原来链表,每遍历一个原,将其取出,放在新的链表的最前端,哪个链表呢?这个链表。
04:11
的最前端。那我画一个图,大家可能就会更明白一点啊,比如说我们还以这个为例。我们还以这个为例,你看我会怎么来实现这个效果,好吧,说了这个呢,有一点点难度啊,首先呢。大家看,我先创建。一个新的节点。这个节点呢,我们取个名字叫做注意听。Reverse。Rivers head。好,然后呢,我开始遍历,就说我这里会有一个指针。我这里会有一个指,我先遍历到这个节点,遍历到这个节点以后,我做一件什么事情呢?我把这个节点取出来。但是我在取出来,取出来取出来过后呢,我取到这来了,取到这这个地方来呢,让他。
05:04
让他他们之间关联起来。当然这个取出来过这个地方可能就没有了嘛。没有了,没有过呢,我事先肯定先要,先要,我肯定是先把这个节点往后面挪一下,再把这个节点取掉。明白意思吧,取掉过,这不是又偏离到一个节点了吗?好把这个节点呢,我们又我这个先往后面挪一下,把这个节点呢又放在,诶这个应该是直接剪过来啊。直接把这个节点放在哪里去呢?好,把这个节点放在这个hi的节点的前面,也就是相当于说让它指向它。然后呢,再让我们这个刚刚摘下来这个节点,再指向我们这个节点。明白这意思吧,好,这不是还有最后一个吗?最后一个我往下移是不是到空了呀?那我再把这个节点剪切到哪里去呢?
06:03
好,再次移动到我们这个节点的。就是这个反转节点的最前面,当然你还得有一个办法,想办法把这一个。Next域指向。这个节点。你看这样做完了以后,你们看这个结结构是什么样子的啊,是不是这样子的就是。Reverse head。它当然这个地方肯定不再是空了嘛,肯定要想办法改变嘛,就是952是不是就达到了逆转的效果。然后第三最后一步,最后一步把hide.next指向rivers hide连个就是原先这个hide呢,就在指向。这个节点好,你现在是不是相当于把整个这个就反转了。大家看清楚我这个这个示意图了吗?不要小看这个题啊,你不动脑筋真真的做不出来。可能有些同学老师这个太简单了,你自去死,你自己去写一写,你就知道没有那么简单。当别人把答案告诉你的时候,你会觉得很简单,当让你自己去做的时候,你一脸茫然,这是所有学生经常犯的问题。
07:10
就只要告诉他,他就觉得啊,这太简单了。只要不告诉他,愁的把头发都挂掉了啊,就这样的人很多。好,我把刚才一个思路已经给大家讲解清楚了,大家大大体明白了没有?思路啊,思路就是刚才我说的一步一步怎么过来的啊,就是不停的摘啊不停的摘。好,最后形成这个链表呢,这个流程就是刚才老师一步一步演示出来的。最后相当于说,呃,你可以这样理解,就是每来一个对吧,从这边摘一个。放到这边来。啊,放到这边来,然后呢,这边再摘一个。又把这个呢,又放在我们这个链表的最前面,最后他这边形成的链表就是这样子的。
08:00
怎么样子的呢?就是由这个rivers hide指向下一个。对吧,然后呢,再让这个指向下一个。最后就形成了952,达到一个逆转,当然做完了以后,其实这边这个节点已经没有了,因为我是摘下来的,取下来的啊,我不会复制一个节点,所以最后这边这边呢,这几个节点其实都已经没有了,就这个节点是没有的了,这个节点也没有了,这个节点呢也没有了,最后再让这个节点。指向这个rivers head的next接一点,那这样子这样子不就达到一个逆转的效果了。思路我讲清楚了没有?讲清楚了啊,讲清楚过后,那下面呢,老师代码将其实现。啊,看老师的代码怎么写,我刚才已经把思路写清楚了。好,现在呢,我们来玩一把啊,就是现在我们要做的工作。我们要做的工作就是将单链表。
09:02
单链表进行什么呢?进行反转。R反转。OK,那现在我们写成代码,Public static void。Reverse reverse什么呢?好,你首先给我一个头节点,这个没问题吧,你给我投节点,给我一个头点过后呢,我首先看你这个链表是不是为空的,或者是一只有一个,如果。当前的啊,当前链表为空,或者或者只有或者只有一个节点,那么就无需反转。是不是就不需要反转,就无需无需反转直接返回?直接返回。OK,那现在我们来把这个条件写写,那就是hide.next如果它等于一个空。
10:03
是不是他现在一个节点都没有,或者什么呢,害。点next。点next。等于空。那说明呃,第一个是代表他一个节点都没有,第二个代表有一个节点,在这种情况下,我们直接返回了,就说呃,不需要再去做处理。不需要再去做处理好,然后下面呢,我们就要开始来做这个工作了啊,刚才我们不是讲到有一个辅助指针吗?刚才是不是我在讲的时候有一个辅助指针在帮我们遍历原先这个。这原先的这一个面表啊,所以说我先定一个辅助指针,先定义一个辅助的一个指针啊,当然也可以叫变量啊,变量它的作用是干什么呢?帮助我们。帮助我们便利。便利原来的这个电表。了解啊了解好,那我现在就写了啊,就是hero。
11:04
Hero node,我就取个current吧,等于什么呢?Hi next,也就是说这个current就有点类似于我们,我们看到这个这个家伙,我把它标粗一点。啊,在在你还没有摘下来的时候,它它实际上就是帮我们遍历原先这一个列表的明白。好,那这个拿到以后呢,我们还需要有一个节点,Hero。No。等于next,等于空,这个节点是干什么的呢?这个节点很重要啊,这个节点是定义当前或者叫指向都可以啊,指指向。指向当前节点的节点的下下一个节点,为什么?因为你这个current。它是指向这个节点的,但是你这个哈,不是后面往后面挪一下吗。
12:02
你挪的时候,在挪之前我要用它一下,在挪之后我才用到下面这个节点,那么如果我挪开了,挪开了又没有进入下一个节点,整个列表就断掉了。知道我在说什么吗?因为你是单列表。所以说我这里需要有一个current current这个next指向当前节点,下一个点,当前节点是哪一个呢?就是current这个节点。因为我要用它。好,最后呢,我们还要定义一个,刚才不是分析出来还要定一个这个revers head吗?能理解我的意思吧,那我就是写了这个东西了啊,那现在呢,我们再来写一个hero node。就是reverse head。等于什么呢?我六一个空的节点啊,因为刚才同学们看到,因为它是个代表头的,所以说我们也有一个空的一个头。好,这边呢,我们写个零名字,昵称都给个空好,这个准备工作就做好了,下面呢,我们开始遍历,遍历原来的链表。
13:11
链表。啊,并并干什么呢?并完成这个工作,刚才我写的这个啊。就这句话了。是不是一句话?就是,呃。诶,小啊病。并从头遍历原来的链表。啊,然后呢,每遍历一个。每遍历一个节点,就完成这样一个工作。就是每编的一个节点呢,把这个写到上面去,每编的一个节点就将去取出并放在新的链表,就是这个hide reverse的最前端,这个地方有点难度,这个大家要动脑筋啊,动脑筋一不动动脑动不动脑筋要很难写出来,那开始写了啊,Y循环。外循环呢,首先我要判断这个current是不是不等于空,如果如果这个current等于空,说明我们已经便利什么呀,结束了。
14:06
能理解吧,所以它的前提是current不能等于空。好,下面呢,我们就让先让这个next指向current的点next。为什么?因为我先保留。我先保留这个current的下一个节点,先先暂时的暂时啊,暂时保存,保存当前节点。节点的下一个节点,因为后面有用,因为后面有用啊,因为。因为后面需要使用。能能跟上思路啊,然后下一个就是current。点next。等于什么呢,Rivers?点next这句话是在做什么事情呢?大家想一想。我让current.next指向rivers,这句话的作用是我解释一下,将current的下一个节点指向新的。
15:12
链表的头部。新的链表的。头节点就是最前端,最前端。因为你不是要把它挂在最前面吗,挂到完了过后,让这个comment继续往后面挪一下。这个我不知道大家能不能看懂啊。这个让current指向下一个。如果你这这地方没看懂会出问题,这个就让cover下个节点指向新的链表的最前端,因为你要你你要反转嘛。翻转完了你卡是不是我后面再挪一下,再处理下一个节点,再翻转下一个节点,让current指向下一个点移动后移次。后移是不是这个道理好么?然后最后这个动作最后一句话啊。最后一句话,当这样做完了以后,其实其实这样做完了以后啊,整个这个链表最终就形成到这个位置了,就是形成到哪呢,形成到这。
16:06
形成到这个位置过后,high.next要指向这个next,就这根线搭起来,我们整个反转工作就完成了。是不是有点绕啊?有点难度啊,同学们,这个是新,呃,腾讯的一个面试题,如果给定大家一点时间,就是我给你,我只给你十分钟,让你马上完成,其实还是有难度的。啊,其实还是有难度,最后连接将什么呢?将这个hide。点next。Hide next。指向指向哪里呢?Reverse head next。啊,这样就实现了什么呢?实现了一个实现了实现反转啊,实现单链表的反转。啊,反转写错了啊反转。好,同学们,我们来走一下吧,那就是hide。点next。
17:00
等于reverse.next那么就写完了。简单吧。但是你如果看不懂,你要想一想为什么啊,刚才老师已经把这个思路一步一步分析出来了,我个人认为分析的还是比较清晰。如果你这块还没拼明白,那你就把这个思路再走一走,好同学们,那现在呢,我们来测一下,看看反转是否已经达到了效果,那这样子啊,呃,我先把,因为这个下面代码也比较多嘛,所以说我先把。呃,这些都先注释一下,好吧,先注释一下。走一个。啊,走一个从这到这儿,我们先注释一下。注册完了过后呢,我直接在这里给大家进行一个反转。好,测试一下,测试一下。单链表的反转。反转功能。对不对?好,首先我们先输出原链表的情况。
18:01
好,这个是没有反转之前的。啊,这是原原来链表的情况没问题吧,我们运行一下。那这个时候显然是按照这个顺序来吗?诶。我看看啊。我看看它下面。原来链表情况列表为空,哦,对不起,因为我这个添加都没有做是吧,所以说我要把这个添加打开。打开过后呢,我在这最下面测试才是对的,不然的话你一个数据都没有,那当然为空,是是这意思吧,好,我们把这个代码稍微的整理一下。好,同学们运心思。同学们可以看到现在呢,原来列表的情况是这样子的。哦,这样子的,为什么上面还有一个打印呢。哦,那我要把这个先怎么样。
19:00
啊,先把删除掉。不然的话,上面还有个空的。好,再运行。好,再看一下,现在是1423。1423,因为你这个是按照顺序来的,现在我要反转了。反转一把。反转。二反转单链表。单链链表OK,反转过后呢,我们再来输出,先反转。反转的话,这样这样反转啊,我们刚才写的这个代码是reverse list。把这个头给我带过去。点get head是不是这个就是反转的。一个方法的调用。现在呢,我们。来例一下,看看有没有反过来啊,运行之。好,同学们,我们可以看到呢,现在的情况是这样子的。诶,我们可以看现在目前的情况呢,有点问题。
20:02
啊,有点问题,它原来的情况是这样的,反转过是为空,这个就不对了,这个就不对了,我们来看看问题出在了哪个地方,问题出在了哪个地方,我们来。好,我们再来运行一下,看代码的情况啊,代码情况。呃,现在的情况是他说反转完了链表为空,我们看代码是哪个地方出了问题,如果不出什么意外的话,应该还是我们这个地方有有问题,我们来检查一下。首先让next指向cover,这个没问题,这个是可以的。Rivers连在这个地方也没问题,然后诶,这么好像少了一句话。少了一句什么话呢?少了一句这样的话,大家看reverse.next。他要指向current。哎,这句话是干什么呀,同学们。这句话是干什么,这句话是不是让我们你因为你你把这个current next指向它过,你还得让你的这个头,就是新的这个节点,那指向current,这样才能连起来嘛,不然的话,那你你不然的话,你永远这个什么都。
21:14
关不起来,就把这个摘下来的,摘下来,这个节点挂,挂不上嘛,所以说我这少了一句话啊,这句话是很重要的,像rivers head连起来这句话干什么的啊,它是将。将这个current连接到,连接到新的链表上,好,这句话如果少了,那永远都是空的了。好,现在把这句话加进去,过后呢,同学们,我们再运行跑一跑,看看代码有没有问题。好,我们看看代码有问题吗?原先是1423,现在变成3241正确。正确,好,同学们,刚才我再说一下这个问题在什么地方啊,可能有些同学没有注意到,我刚才写写的时候呢,少了一句话。
22:03
数据,数据结构和算法就是这样子的,稍微一句话不不对,整个代码呢,那就不正确了,而且调试起来还比较困难,那在哪里,我再找到这句话啊,再给大家说一下为什么。摆在这里,如果我没有这句话,会是怎么样子的呢?会怎么呢?他让这个next指向当前,呃,节点的下一个,然后current next指向revers,就说让他让这个当前这个节点指向了,指向了。这个地方让他执行了,他但是呢,你没有让这个。Riververs head节点指向这个经新加进来的,那那相当于说这个这个节点没有加到,没有真正加到我们reverse head,那riververse head一直都是一个空,能理解吗?就说这条线你进来过后,相当于说你只你只做了把这个线跟下面连接,但是没有把。
23:00
这个rivers head跟他连起来说,它永远是个空的,这句话很重要,所以说呢,这句话我刚才少了就会出问题啊好,呃,那关于同学们,那关于就是单链表的一个反转的腾讯面试题呢,我们就先给同学们讲解到这里。好,待会儿呢,我们再把这个笔记进行一个整理,截取一段视频。
我来说两句