算法：判断链表是否存在环，严谨数学证明快慢指针一定在环上相遇_链表中有环 快慢指针肯定会相遇吗

首先说一下，因为算法的初衷是判断是否存在环，因此环长度默认是未知的，因此选取适当的步长可以提高算法的效率。快慢指针步长分别为2,1，或者3,1，这样的查找次数是相对较少的。

有用两个人不同速度绕操场跑圈的思路来解释，很明显是错的，数学上必然有整数解和必然有解完全是两个天壤之别的概念，连续函数与离散函数也是不同的。

以下给出严谨数学证明。

设慢指针步长为n，快指针速度为m，m与n皆为正整数，则步长之差r=m-n=≥1，环长为x，非环部分长为y，x>=0,y>=0，设慢指针走了i步进入环。

证明1：

 证明的核心思路是明白(m*t-k1)%k2在环上有物理意义：即如果链表有环，这个式子代表指针距离链表交点的距离 ，如果没环，则必然不相遇

证明1是我请教同学+自己思考后的结果，我最开始自己的证明方法更复杂一些，证明某个二元一次方程必定有整数解，则有限步之后快慢指针相遇：

证明：

x=0时，无环，不会相遇，在next = Null时算法终止。

x=1时，某节点自环，必然相遇。

首先，易证明当慢指针刚进入环的时候，快指针此时已经在环中，且距离刚进入的慢指针距离是(r*i)%x，(按照链表环的方向作为距离向量的方向）。

其次，由于在环中起点相距d =(r*i)%x，d∈[0, x-1]且d为正整数

情况0：若d=0，则两个指针在慢指针首次进入环时就已经相遇，必然有环；

下面讨论d∈[1, x-1]的情况，

又因为m-n=r，则下面只要证明d∈[1,x-1]中的任意的一个整数与有限个r相加后的结果能整除x，即可证明两个指针能在环上的某一点相遇。

先看一种简单情况，x=2时，d = 0或1，d=0上面已经讲过了；若d = 1，则说明m与n必然一个奇数一个偶数，r为奇数，则奇数+1=偶数必然能整除x=2，因此两指针会相遇。

下面对x>=3的情况进行讨论

情况1：当r=1时，任意一个小于x的数加上有限个1显然能整除x，成立

情况2：

当r＞1时，

是否可整除，可转化为是否存在正整数A与B满足B*r+d=A*x，即初始距离d+B个步长差r能整除x。

由二元一次方程的讨论，未知数为A、B

1.当r*i0，

因为r>1,r*i0，所以存在正整数解A=r，B=x-i满足方程，即可以整除

2.当r*i>x时，设r*i=d+N*x，N为正整数，则假设B*r+d=A*x无正整数解，则对任意整数A，B

Ax-Br≠r*i-N*x

A-B*r/x≠r/x*i-N

A+N-(B+i)r/x ≠0

取B+i=M*x,M为正整数，使得B=M*x-i>0，则B=Mx-i，M>i/x

A+N-Mr≠0

取A=Mr-N，显然Mr-N>0，Mr是整数，N是整数，则A是正整数。

因此找到正整数解A=Mr-N，B=Mx-i，与假设矛盾。

综上1,2，原方程存在正整数解，即d∈[1,x-1]中的任意的一个整数与有限个r相加后的结果能整除x，两指针必然相遇。

综上所有情况，两指针步长不同时，在有环链表的环中必然相遇。