算法求解!如何判断一个单向链表是否有环路?

今天到网上查一个问题，C 专家编程里的，让我看到了差距，前人大牛啊

-----------------------------------------------------------------------------

用两个指针，一个的步长为 1，另外一个的为 2，从表头开始一起往前走，如果相遇，表明有环路，否则就是没有了。

-----------------------------------------------------------------------------

这个问题应该有很长历史了，《C 专家编程》的附录，程序员工作面试的秘密就提到过这个问题。在这里我试图对这个问题做一个数学的分析。

如果单链表里存在重复的点，则该链表中包含一个环，事实上，可以用下面的图来表示这使我想起 Pollard 的 "rho" 算法，事实上本问题与 "rho" 算法有一个共同点，寻找一个碰撞。

从这个图我们可以看到，如果一个单链表里出现了重复的点，则从表头开始走，无论以什么步调，必定会落到环中。所以我们可以肯定，如果以某个步调走，碰到了NULL，则该链表无重合点。

尝试用两个指针，以不同的步调前进，如果他们能相遇，必定是在环中。假定指针 p 以步调 f 前进，q以步调 g 前进，g>f。则 q 先进入链表的环。有一种情况很特殊，就是：在 p 刚进入环的时候就与 q相遇。这是一个小概率事件，我们排除它，不考虑这种情况。可以认为：

p 进入环的时候，偏移为 a, 而同时 q 的偏移为 b，环的长度为 n。（参考下面的图）

往后， p, q 就在圈内打转，它们在x 步后重合的条件为：

fx + a = gx + b (mod n)
(f-g)x = b-a (mod n)

上式有解等价于 (f-g, n) | (b-a)。

但是，我们在事前不知道 n, 不知道 b-a，所以唯一能确保 (f-g, n) | (b-a) 成立的是 f-g =1。

只要 f-g = 1, 我们就能一定能检测出重合的情况，这是一个充分条件。

而一旦 p 刚进入环时与 q 不等，(f-g, n) | (b-a) 就成为检测重合的必要条件。前面一些朋友说 f,g

互素或 f, g 不同即可的观点是错误的。从 (f-g, n) | (b-a) 这个条件应该能找到反例。但这个我就

留给有兴趣的朋友了。

f = 1, g = 2 未必是最好的，因为如果 "rho" 的尾巴很长，p 要花费很多工夫才能进入环。此外，虽

然步调大的时候，可能要跑好几个圈才能覆盖整个环，甚至在很多情况下不能覆盖整个环，但它跑一圈

的时间也相应减少，足以抵消。可惜的是，分析最优的选择，超出了我的能力范围。