之前同学跟我讨论如何判断一个链表是否有环，以及如何得知环的入口点，说是Programming Pearls （编程珠玑）上面的习题。
以下是我的理解，以及认为大部分文章中关于“定理：碰撞点p到连接点的距离=头指针到连接点的距离” 并不正确，讨论见文末。
当时我想哈希的方式处理，不过这个方法知识理论可行，实际不具有操作性。
后面上网查了资料，问题的解法很巧妙。用速度为1和2的两个指针遍历链表，如果有环的话，这两个指针就会碰撞。bingo, 问题解决。
通过类似的思路，可以简单的计算环的长度，即在碰撞点继续前进，当他们再次相遇时，快的指针比慢的指针刚好多走一圈，也就是环的长度。
这道题让我想到了小学时候的数学题，一个跑得快的人和一个跑得慢的人，他们多久后相遇。
寻找环的入口点方法是从头指针、碰撞点以一样的速度出发（注意不是1和2了），相遇的地方就是环的入口点。很简单很巧妙，但是这个证明这样做为什么会对。
我看了网上的资料，大部分给了算法，然后看了一篇证明，觉得思路不够简单明了。于是我自己想出了如下的方法，用来理解。
首先很容易得到如下的等式，看符号解释即可明白，因为快的指针走的距离是慢的指针的2倍。
$$2(L_{HE} + d) = L_{HE} + kL + d$$
其中$L_{HE}$，为头指针到入口处的距离
$L$ 为环的长度
$d$是入口处到它们相遇的地放的距离
$k$为自然数，快的指针在与慢指针碰撞时走的圈数
通过上式可得 为$L_{HE} = kL -d $， 有了这个等式，我们可以进行如下简单明了的理解了：
速度一样的两个指针，假设指针Head从头指针出发，指针Entry从碰撞点出发，当它们相遇时，Entry走过的路程为$kL - d$，指针Head的距离$L_{HE} $。这不明显相等吗？一个等式，化简一下就出来了，稍微理解一下就可以了。
还有一个提醒是，当快慢指针相遇时，慢指针没有走完环。这个稍微一想，或者列个式子就可以明白了。
参考文章 （“问题3：有定理：碰撞点p到连接点的距离=头指针到连接点的距离，”很多文章都这么写，但是个人认为这个等式不成立，因为它们会在连接点相遇不等于它们到连接点的距离相等。举个例子，环长度为2，头指针到环的入口处为10，显然等式不成立。真正成立的等式，读者自己可以动手列一下。
原文首发于博客园 Hall Of FAME