141、142 判断链表是否有环，并找到环的入口

141  判断链表是否有环                                                                                                                                 点击此处返回总目录

142  判断链表是否有环，如果有环，则返回环的入口节点

一、141  判断链表是否有环   

【题目】

【分析】

快慢指针。

【代码】

【结果】

二、142  判断链表是否有环，如果有环，则返回环的入口节点

【题目】

【方法一】

首先判断链表是否有环，使用快慢指针来做。

接下来，怎么找到环的入口呢？

第一种方法就是，首先求出环的长度n。然后再利用两个指针，一个指针先走n步，然后共同走。当两个指针相等时，共同指向的节点就是入口节点。

为什么呢？

假设环的长度为n，从头节点到入口节点的长度为a。快指针先走n步，然后一起走。当慢指针走了a步之后，快指针刚好走a+n步。因为环的长度为n，所以快指针走a+n步跟走a步效果一样，所以快慢指针刚好在入口节点碰头。

接下来的问题就是怎么求出环的长度呢？

因为在判断链表是否有环时，快慢指针在环内碰头（不一定在入口节点）。这样保持一个指针不变，另一个指针继续再走一圈，当碰头时就知道环有多长了。

代码：

结果：

【方法二】

假设从头结点到入口节点的长度为a，假设当判断链表是否有环时，快慢指针碰头的节点 距离入口节点的距离为b。

因为快指针一直是走两步，慢指针一直是走一步。所以当慢指针走了a+b时，快指针走了2(a+b)的距离，而且两个指针走到了同一位置。此时，如果快指针往回退b的距离，就刚好在入口节点处，即当从头结点走2a+b的距离时，刚好能到入口节点（不一定绕环走了1圈，可能绕了很多圈）。

因为慢指针已经走了a+b的距离，只要慢指针再走a的距离就可以到达入口节点了。

但是我们不知道a的长度是多少，怎么办呢？再次利用双指针。再找一个指针指向头结点，让刚才的慢指针和这个新指针同步走。当这两个指针碰头时，新指针就刚好走了a步。

代码：

这个代码就简单了很多。

结果：