现有一个链表，证明如果存在环，则：使用两个指针同时前进但步长不一样，则能够在有限步之后能够相逢。
题目的意思是我归纳出来的，我的解题思路是这样的：
能够相下逢的意思是：
在走了x步以后，x×S1 和 x×S2 对N同余，其中S1、S2为两个指针的步长，N为环的长度。
(x*s1) %N = (x*s2) %N
等价于：
x*s1 - a*N = x*s2 - b*N
=> x = ( (a - b)*N ) / ( s1 - s2 )
a, b 为指针所走的圈数。a 和b之间的关系于s1,s2有关。
a/b = s1 / s2
这样，上式可改写为：
x = ( a*(1 - s2/s1)*N ) / (s1 - s2)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。