一 目的
本文目的有2点
第一，如果快慢指针相遇，证明链表有环。这个理论是如何推理证明出来的？
第二，代码实现快慢指针相遇，证明链表有环。
二 快慢指针相遇，证明链表有环，理论证明
image.png
下面是针对图中变量做一些解释说明
1.链表起点，假设为 head
2.假设链表有环，环入口假设为 entry
3.起点到环入口的距离假设为 m
4.慢指针一秒走 s 步
5.快指针一秒走 q 步
6.慢指针第一次进入环后距离环入口的距离假设为 a
7.当慢指针第一次进入环后，快指针距离环入口的距离为 b
8.经过 x 秒，慢指针第一次进入环
9.链表环长为 n
接下来开始理论证明推导
- 假设当慢指针第一次进入环后，又经过
y秒后，两指针相遇在某个节点，所以得出下面这个结论
// (b + q * y) 表示经过y秒后，快指针距离环入口的距离（假设没有环，一条直线，一直往前走）
// 再 mod(n) 模上 n(链表环长)，计算出最终停留位置距离环入口的距离
(b + q * y) mod (n)
// 同理下面公式表示经过y秒后，最终慢指针停留位置距离环入口的距离
(a + s * y) mod (n)
// 因为最终两个指针相遇，所以他们距离环入口的距离相等，所以得出
(b + q * y) mod (n) == (a + s * y) mod (n) ------------------ 推论1
- 经过
x秒，快指针停留在距离环入口距离为b的位置处，所以得出以下结论
b = (q * x - m) mod (n) ------------- 推论2
// 解释：q * x 表示经过 x 秒，快指针走过的距离，再减去链表起点到环入口的距离 m 后，
// 得出在环内行走的距离，然后再模除以环的距离 mod(n)，得出停留在环中的位置，即 b
- 同理经过
x秒，慢指针停留在距离环入口距离为a的位置处，所以得出以下结论
a = (s * x - m) mod (n) ---------------- 推论3
4.下面由上述得到的三个推论进行推理
由推论1 (b + q * y) mod (n) == (a + s * y) mod (n)
得出 -> (b + q * y - a - s * y) mod (n) = 0
推出 -> (b - a + y(q - s)) mod (n) = 0 ------------ 推论4
将推论2，推论3带入推论4得 ((q * x - m) mod (n) - (s * x - m) mod (n) + y(q - s)) mod (n) = 0
得出 -> (x(q - s) + y(q - s)) mod (n) = 0
-> (q-s)(x+y) mod (n) = 0
当快指针一秒走2步，慢指针一秒走一步时，得 q - s = 1,即
(x + y) mod (n) = 0，即当 x + y 为 n 的整数倍时，可以保证 (x + y) mod (n) = 0
总结
最终得出结论 (x + y) mod (n) = 0，即肯定存在 x与y，保证 x + y为n的整数倍，使得等式 (x + y) mod (n) = 0成立，即 快慢指针相遇，证明链表有环结论推导证明成功。
三 代码实现快慢指针相遇，证明链表有环
Leetcode题目连接地址 141. 环形链表
public class Solution {
// 链表节点
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
// 链表是否有环
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slowNode = head;
ListNode fastNode = head.next;
// 使用快慢节点
while (fastNode != null && fastNode.next != null) {
if (slowNode == fastNode) {
return true;
}
slowNode = slowNode.next;
fastNode = fastNode.next.next;
}
return false;
}
}
本文参考
