00:00
好,同学们,我们来做几个关于单链表的面试题。面试题,那么一共有五道题,一共有五道题,我讲前面的四个,最后这个题呢,留给同学们作为课后练习好吧。好,我们先来看第一个题,求单链表中节点的个数,或者叫有效节点的。叫有效节点。有效节点的个数,就是说你这个列表里面有多少个节点。就是能够存放数据的这个节点,好,那第一个题呢,我们来一起做一下,这个题是不是特别简单,遍历一下就可以了。就我便利一把就可以好,这个题呢,我就不做思路分析了,直接上代码。好,同学们,接下呢,我开始在哪里写呢?因为这个方法它是通用的,所以说我直接写在这里好吧。直接写个方法干什么呢?啊,我们写一个方法,方法干什么呢?获取到获取到单单链表的有效啊,或者叫节点的个数。
01:01
个数,那么如果是带头节点的这个链表呢,要把头节点去掉,因为头节点它没有存放数据嘛,啊就说如果是带。带头。头节点的这种链表。链表需要。啊,需要干什么呢?需要这个不统计不统计这个头节点,就这意思啊头节点。请同学们注意这个问题。好了,那现在呢,我们直接写写代码了,Public static int get n。长度认识OK,那现在呢,你只需要给我传一个节点过来,我就可以搞定,说我接收的是一个什么呢?同学们看我代码啊,同学们看我代码,诶这个地方写错了。哦,我做一个文档注释,就说这个hide呢,就是这个链表的什么呀,链表的头节点。
02:02
OK,那这个返回的就是呢,返回的就是有效,有效节点的个数。是不是很简单呀?来,同学们,我们来做一个判断。好,我们首先判断这个链表为不为空,如果next,它直接等于空了,说明什么问题?说明这是一个空链表。这是一个带头节点的空链表,那这个时候不用多说,直接返回一个空,返回一个零就行了。好,否则呢,我们现在来进行一个统计啊,这个是认识,然后呢,我们做一呃定义一个定义一个辅助的变量,那么这个变量呢,我们这样写叫hero node current。等于hi.next没问题吧,现在呢,我们便利一把就可以了,Y循环。外循环,只要这个current。
03:02
它不等于空,大家明白我是说什么吗?大家想一想啊,也就说你现在指向head的下一个节点,只要current不等于空,我们怎么办呢?诶,我们就让这个Les加加。累积一下,然后让这个current指向下一个便利嘛,哎,便利点next这个就体现出便利了。这个形式便利,当我们这个while循环结束以后,返回return,返回这个认识就可以了。好,同学们,这个代码就写完了,我也没做分析啊,因为这个代码特别简单,说白了就是便利一把,便利的时候呢,要不要把这个头节点算进去就可以了,你看这个地方就体现出我们有统计头节点。是不是这个道理啊,因为我直接让current指向还点next,注意啊,这里这里我们没有统计头节点。
04:00
没问题吧,同学们好,同学们我们试一下吧,我们试一下来,我们测试一下代码,测试一下哪个程序呢?就是求单链表的有效节点的个数。演示一下system。好,我直接调这个方法。那么这个头节点在哪里呢?这个头节点实际上是在单链表的。一个属性是不是,那既然如此,这个单列表投递又是个私有的,我们怎么办呢?好办,我们给他提供一个方法就可以了,对不对?我们写一个方法public。返回一个hide。No,对吧,我们写一个get head。或者或者同学们这样写也可以对吧,你们都学过这个方法,把快捷键,然后呢,我们这直接写个R。是不是,那这个直接返回一个get一个head不就完了吗?这样写更快一点,好,这个就返回。
05:05
返回头。头节点,OK,那返回头节点,同学们想一想,现在呢,我们这个地方就应该这样写了,Get。然后呢,用这个single。点get high。是不是他把投递点返回给这个方法,这个方法统计出来就行了,那现在想想,我们如果输出的话,一共有几个。是不是你删了两个,你删了两个,现在应该有几个,有两好我们运行一下。同学们看返回的这个一共有两个,所以说我们这做一个提示信息就是有效的节点个数等于。加起来就可以了。便利啊,一共有两个,好,现在呢,我们趁热打铁,我们把这个查找单链表中的倒数第K个节点,你给他写了,这是这是一个新浪的。
06:00
呃,关于单链表的面试题,我们来完成一把。写个。好,同学们现在要查找单链表的。倒数第K个节点。同学们想你会怎么做?你会怎么做?你的思路是什么样子的呢?好同学们,那这个因为也比较简单,我就直接上思路了啊,我就直接上思路了,好,思路如下。第一个。第一个首先呢,我们写一个方法会接收我们编写,编写一个方法接收什么呢?接收这个high的节点。啊,我们叫接收。接收hi的这个节点,同时呢,同时接收一个index啊,这个要说明一下啊,这个index表示的什么呢?Index表示表示的是倒数。
07:03
倒数第。Index个节点。明白我的意思吧,第三个同学们看你你再进,因为我们这个是单链表,它不可能从。这个链表的最后逆向来进行这个便利。因此我们要这样做,先把。先把链表从头到尾。便利一下。那么我把这个链表从头到尾遍历,大家想象其实就是这个意思。比如说我们以以这个链表为例,我是从这个位置开始便利啊,从他的这个有效节点开始便利,我便历出来过后呢,我看他一共有几个节点。有几个节点,然后呢,我在。得到它的节点个数以后,是不是下一步就好变了,我就用它的N减去index变成这么多个,是不是就到倒数第几个了呀。
08:02
大家明白我在说什么吗?好,不明白,我写代码啊,把链表先从头到尾进行遍历,得到或者得到什么呢?得到这个链表的。链表的总的长度。啊,总的长度。对吧,当然这个总的长度,其实我们这个get认识已经拿到了。所以到时候你调这个get就可以了,说白了这帮你调用一下这个方法就行了。好,下一步当我们得到这个认识size过后呢?我们再怎么得到?得到,哎,我们这样说啊。得到这个赛子后赛之后,我们从队列哦,从这个链表。的第一个,第一个开始遍历,便利多少个呢?便利size。Size减index就行了。
09:00
是不是这个道理啊,比如说呃,打个比方,你要便利倒数第一个,是不是就S减一你就便利,你就便利到这个位置。便利到这便利到便利到这个位置就可以了啊,就得到了,就得到。就可以得到。好,现在呢,老师就把这个代码给大家演示一下就可以了,Public static。13题课好,然后呢,我们返回一个节点啊,我们这再加一个就是如果如果如果找到的话呢,诶我们就返回这个节点,找不到我们就返回一个空好吧,对吧,如果找到了则返回该节点,否则返回一个空就行了。好吧,那现在我们反回去,我就写写个叫find方法名,我这样写啊,Find last index啊,Last。呃,Node吧,就是返回这个发现最后的那那个last的index的一个节点。
10:03
按倒数的啊,倒数的节点,那现在呢,你给我传一个para no。是不是你给我穿一个,然后呢,Index给我。这个没问题吧,没问题,好,现在呢,我们先判断判断,如果这个。链表为空,我们就不走了,如果链表为空,返回什么呢?返回这个空就行了,链表为空,你没法没法往下面继续走了吗?说head.next。大家跟上我的思路啊,如果它等于空,那这个时候我们直接返回一个空。表示什么呢?没有找到吗?没有找到,否则我们继续往下走好,第一次便利,第一次便利便利啊,便利得到什么呢?得到链表的长度或者叫个数啊,节点的个数。这个对我们来说是不是已经很简单了,我直接int一个size,等于调用我们刚才那个方法就可以了,这个方法就head。
11:08
拿到了,拿到过后,拿到过后,然后呢,我们第二次第二次第二次便利便利多少呢?便利这么多个。便利到这个位置。变异到这个位置,位置就是我们倒数的地。DK个DK个节点能理解吧,那现在我们就开始直接来来组成代码啊,那先做一个,先做一个数据的校验,先做一个index的校验。校验什么?什么叫校验呢?就是看看它的这个数据是不是合理的啊,比如说我们看如果index你给过小于等于零,那我肯定没法找,你不能说我找一个倒数。
12:00
啊,倒数第一个的咱们就没法做倒数第一个嘛,至少你的倒数第负一个咱们也没没法弄是吧,或者你的index。大于多少呢?大于了一个size,咱们也不可能找到,比如说我统共才五个。你可以说倒数第五个,但是你不能说让我找倒数第第五个,我没有好,在这种情况下呢,我们就直接。返回一个空,就是找不到,比如你要找倒数第六个,我本身只有五个,那我就找不到,好,下面就可以来开始编译了,好,现在呢,我们仍然定义一个辅助变量。啊,我们要定一个辅助变量。那来了啊,Hero node,就是我用一个什么变量呢,用一个。Temp,当然这个temp我也改个可以叫别的名字对不对,就说相当于说我这有一个辅助变量,让它不停的一个去找。就一个一个去便利就行了,明白吧,好,现在我们要写一个current。
13:01
Current等于什么呢?hi.next也就是说我先让这个current指向啊,如果是按这个情况来看的话。我把这个再粘一份啊。给同学们演示一下,有些同学可能看起来有点吃力,所以我再这么再演示一下,也就是说我上来过后呢,先让。一个辅助变量指向我们的,呃,第一个有效的节点叫current。找到以后呢,我就开始变往从这开始走,数几个呢,数size,那就是那个size减去index。就到这,比如说我现在要倒倒数第一个,那实际上我就走在这个基础上走向几下呢?在这个基础上下一个再下走两下就可以了,是不是这个道理啊。好,所以说呢,下面有了这个东西过后,我们来便利啊,便利走几下呢,就用for循环。
14:01
啊,For循环一下for循环。Four。循环定位。循环定位。道。这个倒数的倒数的这个index怎么怎么来定位呢?For循环来啊int I等于零,I小于,看这个代码怎么写的,Size减去index。I加加,然后这边它主要的目的就是往下移动,所以说current呢,就等于current.next。我们来看看这代码有没有问题,比如说我现在一共有三个。三个有效数据,我现在呢,已经指向到了这个位置,我要找倒数第一。一个,比如说我要找倒数第一个,我应该移动几下呢。移动一下,再移动一下看就找到了是吧,那你看我这个是不是移移动了两下零塞子。
15:03
呃,如果从这来看是S减去一,因为我要找倒数第一个嘛,它应该等于二,那如果这里面变成二。变成二的话,同学们看你是不是移动了。一下移动了两下,因为这是小,没有包包,没有包含这个说是实际上移动了两下,对不对,那就刚好到我们倒数第一个了,能理解不?好,我就把这个撤回去了啊,那现在呢,当我们这样做完以后,其实这个数据就找到了,直接返回啊,Current找到了。就倒数的第几个,好,我们来测试一下。我们测试一下,测试一一下,看看是否得到了,得到了倒数第K个元素啊,节点节点,好,同学们,我们来玩一把吧,那现在呢,我们来做一个小小的测试,比如说我现在呢,有个hero。Hero node。
16:00
好,我测试一个啊,比如说我现在这个result等于什么呢?用刚才的这个范的。我比如说头节点仍然是用single。点get给他返回去,比如说我要得到倒数第一个。同学们,那倒数第一个应该是哪一个呀?倒数第一个,从我目前来看,倒数第一个是不是应该是。无用啊。是不是应该是无用?因为我目前是吴用是最后一个嘛,所以说我输出。输出好我写啊,就是到我就直接写result了,等于把它输出来给大家看一下,这个应该是无用,我们运行至啊。就叫。叫做测试吧,啊就是测测速好运行。我们看是不是找的是无用,我们发现的确是倒数第一个确实是无用,那如果说我把这个改成二呢。是不是倒数第二个,倒数第二个其实就是玉麒麟。是不是这个道理,好,我们运行值。
17:02
我们运营形式,诶我们发现呢,的确找的是预麒麟,那如果说。如果说我写的是倒数第三个有吗?没有,那这个地方就会返回一个空。返回一个空。因为你你没有这个嘛,所以说你这一运行呢,它返回的是一个空。是不是?好,这个说明我们这个代码是没有问题的,对吧,没有问题,好,那么这样子呢,我们就把前面的。呃,第一个题和第二个题给同学们讲了,好,那第三个题和第四个题呢,我们放在下一个视频为大家讲解。
我来说两句