14-尚硅谷-Scala数据结构和算法-单向链表-有序插入节点

假如我在这地方又加了一个二号。比如说我有个HERO4。好，二号宋江二，及时雨二。那现在呢，我在这儿加一个四的时候，它就出现这么一个问题，那同学们看。他在他默认是没有排序的。看到没有？它是1342。那现在我想对这个做一个改进，就是在添加的时候呢，我们把它改进成一个什么方式呢？就是我们保证在添加时能够是有序的。保证它的一个编号是有序的，好，我们我们不在这上面改，我们单写I2啊这样的呢，能够保留原先的代码，好我们来写第二种方式了。第二方式，我们要动脑筋呢，同学们看看这个代码应该怎么写啊？好，我先把这个拿过来。好，把这个拿过来，把这个拿过来过后呢，我们来做一个小小的判断啊，我们来做一个说明。

先说一下这个思路。现在这个思路，整体这个思路仍然是不需要有什么变化，只是你在找这个节点的时候。要去要去判断哦，我们这儿还有一个问题啊，第二种方式，在添加英雄时，根据排名将英雄插入到指定位置，我这儿还有一个要求，还有一个什么要求大家看。就说如果有这个排名，则添加失败。就假设你已经有一号了。你再加一个英雄，他仍然是编号为一，这个就要给他一个提示信息，我们把这个呢，要给大家做一下。好，把这个一起完成。好，前面我们来写爱二，爱二呢，我们还是跟前面一样，先拿到一个节点。还有节点，现在我们来做一个判断啊，因为头节点不能动，所以说我们需要一个临时节点这个。

要把。这个拿过来我就。形式好，然后我要做一个说明。我这做说明，注注意啊，注意注意我们找添加位置，我们在找。这个添加位置。添加。添啊，添加位置时，位置时。啊，四四。四将。是将这个节点。节点。加入到诶。呃，节点加入到哪里呢？是将这个节点加入到这个temp的后面。大家知道为什么要这样加吗？

因为你你在进行这个比较的时候是要。加入到这个temp的后面，这是个前提，因为我们在加的时候，如果如果这个加入到temp的前面，我们是加不进去的。所以你在比较的时候，一定是比较temp的下一个元素跟当前这个元素的一个关系好，因此我们在比较的时候呢。注意听。因此。OK。因此。因此在比较时。比较，呃，比较。比较时是将当前的。哦，当前注意听到当前当前的这个he load he load和temp.next。节点进行比较。啊，比较。好，现在呢，我开始来写这个代码，主要是找这个位置，找这个位置好，那现在呢，我们仍然是用一个外循环来做Y循环。

好。还是一个处。前面呢，我们有一段代码，我们来看看，这个仍然可以拿来用。对，仍然可以拿来用。如果temp.next等于空了，那说明已经到列表最后了，那可以加进去。啊，那么还有一种可能性，就是有一种可能性就是这个，因为刚才我们说如果有这个排名则添加失败。那我们还得设置一个标标记。这个有点慢慢理解啊，假如我们认为是这个是没有的。就是这个flag的作用是什么呢？Flag是用于。用于判断。是否？是否这个编号已经存在了，就是判断是否英雄该，该英雄该。

该英雄的编号编号已经存在。我要设计这么一个，因为我默认是不存在的。默认不存在。但是不一定呢，我不知道有没有说说默认不存在，默认为false。好，下面呢，老师就要开始做一个判断了啊。如果。找一个位置。我们现在要找位置，怎么找呢？就是如果这个temp.next的点no。大家看这个代码能看懂吗？大于了hero.no。好，我们还要假定，我们还要假定这个顺序是编号从小到大。因为从大到小肯定。变就变化了吗？我们有一个假定的条件。

这个条件假设说我们假定这个编号。从小到大排。大家注意听啊，那我问大家，如果这个条件成立。说明什么问题？是不是就应该插到temp后面了？这点大家能不能绕过来？我再说一遍，我现在要找temp的下面后一个啊，因为如果我找到的前面我是加不进去的，因为它是单向的，你这根本就加不进去了，所以说我这个条件一旦成立，就说明位置找到了。有点不好理解是吧，我们待会儿看位置找到了。我举个例子吧。我举个例子，大家不要着急啊，我举个例子，假，假如现在这个条件一旦成立，就是位置找到了，应该加到哪里呢？就是当前这个节点。当前这个节点。节点应当加入到。应当加入到哪个地方痛后？

为什么这么说？我们举个例子，大家看这个条件啊，朱婷，那我把这个条件拿过来。我说了，代码都不难。但是呢，就是理解的问题啊，我们把这个条件给他搂一圈。比如说目前我们有这么一个情况，说这里是三号人物。这是四号，其他我不变化了，现在我要加一个什么节点进去呢。现在我准备加入的节点编号为二。假如我把这个拿过来。我复制一份，假如我们要编号为二，注意听。编号为二，那编号为二呢？假设这编号为二的一个人物来了啊，那你看，首先我上来过后先让temp。先让这个temp指向了我们的head，这个没问题，因为我不能动head。然后呢，我先让这个temp的下一个一。

跟这个二比较。一大于二吗？不大于二，不大于二说明它至少一不大于二，至少说明这个二不能加到，加到这个temp后面，不能加到不能加到这个temp后面，就是因为不能加到你这个一的前面是不是。因为我是让跟下一个比较嘛，因为你这个一。temp.next不就一吗？一不大于二，所以说它不能加到这个temp的后面，如果加到temp后面，这个二不就在一的前面了。好，紧接着这个temp往后面挪一挪了一位。挪了一位过后，这个臀部的下一个是不是就删了？能理解吗？三好，三是不是已经大于二了，是不是说明这个二这个节点就应该插在这个一和二之间呢？也就实际上就插在这个臀部的后边，能理解吧。好，现在的问题来了，现在只要这个条件OK，就说明位置找到，应该加入，后面这个大家应该不会有什么疑不，不会什么疑义，对不对，肯定是正确的。

好，这个位置就找到，位置找到是不是就该break出去了。为什么要break，因为你位置找到你就赶紧走，你不能在这马上加加构这个，这个逻辑不好处理了，所以马上就退出去，这个temp就已经找到了。还有一种情况。L if，如果temp.next.no它等于了hi.no这说明什么情况？哪个同学告诉我？是说明你这个链表里面有一个节点的编号，跟你这个要插入的这个节点编号一样啊。是这个意思吧，好，这说明已经有了，已经有这个节点了，没问题吧，那这个时候是不是我们也应该break出去？因为有，我知道不要着急，肯定是要肯定是要离开了，因为就相当于说人家也有一个送当老大的一号，你你要当老大，那不是打起来了嘛，对吧，所以我就退，但退出来之前是不是要告诉别人这个flag说对不起，这个地方真的是有了。

是这意思吧，因为你这样才能知道我这个加不进去是什么原因。对吧，好，所以说同学们看整个这个Y循环以后，有两个，一个是temp指向了该加的位置，但有一种情况苏老师。假如这个条件不成立，这个条件也不成立。是不是只有一种可能，就说刚好他应该加到屁股后边去，而你这个衣服如果是从这儿退出来的。是不是这个臀步就应该是指向我们链表的最后？能理解吗？所以说你臀部在最后，是不是你也应该加在臀部后面。好，思路就这样子的，那到此我们整个用break able包起来就稍微有一点绕啊，但还可以。

待会儿呢，我让你们会消化一下，稍微消化一下好包起来。包起来以后，包起来以后下面呢，我就做一个工作，我就做一个什么工作呢，我要判断一下，如果这个flag。它是这个为真了啊，如果这个取反。哦诶诶不虚反，诶如果这个flag仍然保持一个false，说明这个地方是不是应该是是可以加的。是是可以加吧，如果是else说明。是不是他就已经为已经为，因为我取了下反吗？说老师为什么你这样，如果我这样写的话，我这就写了一句话不划算，所以说我这样写的啊，当然你如果这样写也可以，就代表不可以加，这样写可以啊，不可以加。不可以加入，加入我就直接提示一句话，这样写行，同学们可能喜欢这种写法啊，就写写写句什么话呢，就说插入的待插入的。带插入的这个英雄啊这个。

英雄，英雄编号。啊，英雄编号。这个把它输出来已经存在。已经。已啊，已经存在。不能签加啊，已经有了有了。哦，不能加入。不能加入，好，然后我在这个地方呢，就把这个信息打出来了，那就是百度，那就是应该是这个你hero.no嘛。对吧，但但是这个地方我们要格式化一下。格式外向好，否则就说明他确确实实呃是仍然保持一个false，那这个时候我们就加入。啊加入，那加入的时候应该怎么加呢？同学们，来，我们来看看这段代码的关键。OK，怎么加进去，同学们，是不是你只需要实现这个，把这个地方指向它。

然后再把这个地方next指向它。就可以了。那么我们应该怎么加，是先加这条线。是先动这条线还是先动这条线，同学们？是不是应该先动这条线？大家记住一个原则。你在进行这个添加删除的时候，优先考，在加入的时候一定要先把先不要去动这个链表本身，如果你先加这条线，同学们那就完蛋了，一旦加了这条线，这条线是。拿不到了。为什么拿不到？因为你访问不到这个节点了呀。是不是？好，这面有一个添加顺序，大家一定要注意啊，所以说我们这儿提示大家一下，添加顺序很重要，那我写到这添加的时候应该这么讲，注意顺序。注意。注意顺序问题，那这个时候我们应该增加了。

嗯，先让这个新的节点。Hero load.next它指向谁？Temp点什么？Next，非常好，非常好，然后temp再点next指向谁？Hero very good啊，同学们。那这个老想是什么东西啊。好，这个就加进去了，加进去是不是这个事儿就。就完成了呀，完成好，同学们现在呢，我们用第二种方法来加，看看代码有没有问题来，同学们，那现在呢，我把整个全部改成几呢，改成二。好，那就二。哦，我这个还不动它，因为我要保留一下啊，待会我不然的话，如果想看到以前代码还麻烦了把它注销，然后改成二。改成二，其他不用改，改成二。改成二，好同学们，我们以这种方式来添加的话呢，我们来执行一下。

同学们看这个时候顺序。诶，大家看死在这里面了，哪哪错了。哪儿错了？大家知道我哪写错了？我们整个这个操作完了，有一件事情忘做了，哪件事情忘做了，同学们这是一个死循环。Very good，因为你这Y循环过后你没动过啊，就一直是循环死循环在这。对吧，所以说你要做一件什么事情呢？就是temp等于temp next，刚才这句话很重要。不然就死循环，这句话不能丢啊不能丢，注意。好，我们再来执行一下运行。好，同学们看到。1234，这就是一个有序的了。那我问同学们，再说一个问题，如果我要从大到小排，应该怎么做呢？

如果是从大到小排哪个地方改一下就可以了。是不是把这个改一下就可以了。对吧，如果我这样加，我们看看这个逻辑是什么样子的。是不是4321呀。诶，这就是我们要的一个效果好，同学们，那关于这一个，就是我们所说的这个。就是这个链表的显示和添加，我们就说完了，我们先截取一段视频。