当前位置:   article > 正文

链表经典面试题下

链表经典面试题下

目录

如有帮助,还望三连支持,谢谢!!!

题目一:141. 环形链表 - 力扣(LeetCode)

题目二:142. 环形链表 II - 力扣(LeetCode)

题目三:138. 随机链表的复制 - 力扣(LeetCode)

题目四:链表的回文结构_牛客题霸_牛客网 (nowcoder.com)


如有帮助,还望三连支持,谢谢!!!

书接上回,上次我们讲了一些链表的经典面试题目,并留下了一个问题,那么今天我们就来探讨一下这个问题,并且来讲一下剩余题目。

题目一:141. 环形链表 - 力扣(LeetCode)

上篇文章我们讲解了判断一个链表是否带环的问题,我们当时讲解的思路是:快慢指针,即定义两个指针:fast,slow,快指针一次走两步,慢指针一次走一步,链表如果有环的话快慢指针一定会在环中相遇。并且我们讲解了一定会相遇的原因:本质就是追击相遇问题。

并且引出一个问题:

我们证明了fast走两步一定能追上,那fast指针一次走3步,4步......n步呢?还一定能在环中相遇吗?

我们来看一下fast一次走三步的情况:

经过我们上面的分析,我们在假设追不上的情况存在时,推出了永远追不上的情况:

N为奇数,并且C为偶数

那么这种情况存在吗?我们接着来看下面的分析:

经过上面的分析,我们得出:当fast一次走三步时一定能够追上。

至于fast一次走4步,5步......与上面分析结果大同小异,这里只抛砖引玉,读者有兴趣可以自己深入研究一下。

题目二:142. 环形链表 II - 力扣(LeetCode)

乍一看:这不是和我们第一道题目一样吗?确实十分像,都是判断链表是否存在环形链表,但是这个题目要求如果有环,返回开始入环的第一个节点,这个要求还是有意思的。

那么我们还是先说思路:快慢指针,慢指针一次走一步,快指针一次走两步,先判断链表是否有环

如果有环的话,创建两个指针,一个指针从head节点开始,另一个指针从相遇点meet开始,两个指针每次都走一步,两个指针相遇的点就是链表入环的第一个节点。

代码如下:

那么,为什么meet和phead指针一定会在链表入环第一个节点相遇?讲解如下图所示:

那么,相遇时slow有没有可能会在环里走了超过一圈?

不可能,fast速度是slow的两倍,两者最远相距C-1,所以slow不可能走的距离超过一圈

即为L距离就等于meet在环中转x-1圈,再走C-N,所以说meet和head的相遇点一定是链表入环的第一个节点。

题目三:138. 随机链表的复制 - 力扣(LeetCode)

这道题目,也是考察单链表,但是有意思的是链表的每个节点有一个random指针,只想链表中的任意节点或者是空指针。

以我们现在知识水平,用c来写有点复杂,但是我们有一个比较简单的方法:

遍历原链表,复制链表的每一个节点,并且尾插到链表对应节点的后面,然后在完成对应的操作,最后把复制的节点拿下来组成一个新的链表。

链表复制,并且尾插到对应节点的后面,这个操作我们之前讲过,也写过好多遍了,不再赘述,但是random指针该如何控制呢?

确实,这道题目的难点就是random指针的指向,但是我们这个方法完美的解决了这个难题,为什么呢?如下图所示:

我们怎么控制节点一的random指针呢?

只就是这个方法的巧妙之处,只需用一行代码,便可轻松的控制复制节点的random指针的指向。

代码如下:

控制random指针时要注意:若对应节点的random指针指向空,那么复制节点的random指针也指向空即可。

题目四:链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

这道题目,看似难度是困难,其实就是一个纸老虎罢了。这道题目无非就是把我们之前讲的题目糅合在一起,形成了一个新的题目。

我们来一步一步的拆分这道题目:

判断链表是否有回文结构,也就是判断链表节点的值是否左右对称。

如上图所示,这两个链表都是回文链表,那么该怎么判断一个链表是不是回文链表呢?

首先,回文链表是对称的,所以我们要先找到中间节点,并返回链表的中间节点。

然后,我们在以中间节点mid为头结点,把从mid往后的链表进行反转。

进行这两步后,链表变成了这个样子,这时我们在分别从phead,mid开始遍历链表,对比两者节点的值,如果相等,就是回文链表,如果不相等,就不是回文链表。

这时又小伙伴可能会问:上图第二个例子,当phead指向第二个节点时,mid指向倒数第二个节点,那么phead->next指向哪一个节点呢?这个我们要回想我们之前讲过的反转链表的实现过程,它的指向如下图所示:

所以说,我们的思路没有问题,代码如下图所示:

这段代码看似很长,但其实思路并不难以理解,就是把一道题目分成了我们之前讲过的一道道的小题目。只要熟练掌握了我们上篇文章讲解的题目,那么这道题目就非常容易了。

至此,我们链表的经典面试题已完结,希望读者能从这两篇文章中有所收获。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/623389
推荐阅读
相关标签
  

闽ICP备14008679号