【证明】判断链表存在环——快慢指针一定能相遇

问题

在面试题中常有这样的考察链表题目：

如何判断一个链表中存在环？

思路

常见的有3个思路：

• 1、暴力遍历
  时间复杂度：O(n^2)
空间复杂度：O(1)
  双重遍历，外循环依次遍历每个结点；内循环用新指针从头遍历此结点之前的所有结点，判断是否有相同结点。

• 2、hash存储遍历过的结点
  时间复杂度：O(n)
空间复杂度：O(n)
  只需遍历一轮，每次遍历完一个结点将其加入hash_map，遍历时从hash_map中判断是否已经出现过。由于hash_map存取时间O(1)，所以用牺牲空间换时间的方法可以把时间降到O(n)。

• 3、快慢指针
  时间复杂度：O(n)
空间复杂度：O(1)
  神奇的快慢指针法可以不另外开辟空间的同时只需要一轮遍历就可以判断环的存在。

  具体思路：
  使用一快一慢2个指针，均指向头结点。慢指针p1以每一步移动一个结点的速度前进，快指针p2一步移动2个结点。

  (1) 若不存在环：
  p1、p2均会到达链表尾部NULL，判断结束。

  (2) 若存在环：可以把环看作操场跑道，把慢指针p1看作龟🐢，把快指针p2看作兔子🐰。
  这是一个标准的龟兔赛跑/追及问题。跑得快的兔子一定会绕圈追上还在上一圈/上上圈/…的乌龟！

以上3种思路的代码实现都不难，就不赘述。重点在于快慢指针的分析。

思考

快慢指针的思路可以感性地理解其意义，但如果深究的话，会有以下的疑问🤔️：

1、为什么p1速度为1和p2速度为2就一定能保证快慢指针相遇？

2、如果p1速度为1，p2速度为3也可以判断链表存在环吗？

证明

一、对于第一个问题，有2种证明方式：

1、递归证明

case 1：快指针与慢指针之间差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。

case 2：快指针与慢指针之间差两步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况。

case 3：快指针与慢指针之间差n步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差n+1-2即n-1步。重复这个过程，直到快指针和慢指针相遇。

所以快指针与慢指针必然相遇。

2、数学证明——线性同余等式

符号定义

• l：环的长度
• s0：环的起始位置
• r1：慢指针p1的移动速度
• r2：快指针p2的移动速度
• s：p1刚进入环s0时，p2距离p1的距离（0 <= s < l）
• m：p1刚进入环s0时，再移动m步即可与p2相遇

即可以得到相遇时p1的位置 s0+(m*r1 mod l)，p2的位置 s0+((m*r2+s) mod l)。

至此，
判断快慢指针能否相遇的问题转化成 =>
寻找一个 m，使得其满足如下等式
(m*r1)(mod l) = (m*r2 + s)(mod l)

以上等式可以进一步化简：
m(r1-r2) = s mod l
m(l+r1-r2) = s mod l(*)

*式就是线性同余等式！

根据线性同余等式的性质，为使得自变量m有解，s要能够被 gcd(l+r1-r2, l)整除！

若r1=1，r2=2，则gcd(l+r1-r2, l) = gcd(l-1, l) = 1。
而对于任意的s，总是能被1整除的。所以m有解，即可以找到一个m使得p1、p2相遇！

二、证明完第一个问题，第二个问题也就迎刃而解了。

同样可以用线性同余等式来证明，r1=1、r2=3或者是其他速度究竟行不行。
从上面我们知道，要想判断有环，m就必须有解，即要使得s能够被 gcd(l+r1-r2, l)整除。

1、首先证明r1=1，r2=3行不行：
当l是奇数，gcd(l+r1-r2, l) = gcd(l-2, l) = 1，对于任意的s满足条件。
当l是偶数，gcd(l+r1-r2, l) = gcd(l-2, l) = 2，s是偶数时可满足条件/s是奇数时不满足条件。

综上所述，r1=1，r2=3不能判断链表是否有环。

2、对于任意的r1，r2，需要满足什么要求呢？
这里仅考虑普适情况（任意s、l均成立）。

我们可以知道相邻整数的最大公约数是1，而1可以整除任意整数s。
可得r2-r1 = 1时，可满足gcd(l+r1-r2, l) = gcd(l-1, l) = 1，可以用于判断链表存在环。

综上所述，只要满足p1、p2速度差为1，即可判断链表存在环。
而最常用的就是r1=1、r2=2，是为了减少访问链表的消耗(相比r1=10 、r2=11)。

如果对您有帮助的话，请点个赞吧！！ 😋😋

参考资料
[1] 为什么用快慢指针找链表的环，快指针和慢指针一定会相遇？