Floyd的cycle-detection算法解析(原创)
要解决的问题是： 如何确定一个链表中时候存在环，如果存在的话，环的起点在哪里? 借用这张经典的解析图 Floyd 的算法又叫做龟兔赛跑算法，那么我们就用龟兔赛跑来解释。 我们假设乌龟和兔子的速度是1:2，然后 假设乌龟的兔子在赛道的某一点相遇了 。(相当于他们直线跑入一个环形赛道，然后在赛道的某一点相遇了)那么因为他们跑得时间是一样的，即他们跑得路程1个是i，另一个是2i。借用上图的表示，我们有如下等式： 1) i = m + p*n + k 2) 2i = m + q*n + k 这里的p和q分别是兔子和乌龟在环里跑得圈数。q>p 解上面的等式去掉i,我们就得到下面这个重要的等式： m + k = (q-2p) * n (等式一) 因此，如果我们能够证明至少有一种k, p, q的值可以使得这个等式成立，我们就证明了这样的m和n的是存在的。 (如果环存在，即上面等式成立，m和n的值是确定不可变的，只有k,p,q是可变值。) 进而也就证明了乌龟和兔子的相遇是成立的。 这里我们只要使 k = m*n-m; q-2p = 2m; 也就是说存在k,q,p的确定的值的组合(因为他们都可以用m和n表示)，使得上式成立。 下面我们来解决第二个问题，即环的起点在哪里。 让我们再加一只乌龟进来，叫做乌龟二号。 乌龟二号和乌龟一号有同样的速度。当乌龟二号在链表起点时，乌龟一号和兔子相遇在环内的K处。 现在，当两只乌龟一起走m步时，即乌龟二号到达了环的起点，这时候 乌龟一号走的总路程 = m + p*n + k + m 根据等式一计算m+k得出： 乌龟一号走的总路程 = (q-2p) * n + p*n + m 即 乌龟一号走的总路程 = (q-p)*n + m 所以当乌龟二号在环起点的时候，乌龟一号走过了(q-n)圈个环，再加上m的路。所以乌龟一和乌龟二第一次相遇的时候的点就是环的起点。 参考 http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare