链表经典面试题下

目录

如有帮助，还望三连支持，谢谢！！！

题目一：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指向哪一个节点呢？这个我们要回想我们之前讲过的反转链表的实现过程，它的指向如下图所示：

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

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

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