快慢指针相遇证明链表有环理论推导证明

一 目的

本文目的有2点
第一，如果快慢指针相遇，证明链表有环。这个理论是如何推理证明出来的？
第二，代码实现快慢指针相遇，证明链表有环。

二 快慢指针相遇，证明链表有环，理论证明

image.png

下面是针对图中变量做一些解释说明

1.链表起点，假设为 head
2.假设链表有环，环入口假设为 entry
3.起点到环入口的距离假设为 m
4.慢指针一秒走 s 步
5.快指针一秒走 q 步
6.慢指针第一次进入环后距离环入口的距离假设为 a
7.当慢指针第一次进入环后，快指针距离环入口的距离为 b
8.经过 x 秒，慢指针第一次进入环
9.链表环长为 n

接下来开始理论证明推导

1. 假设当慢指针第一次进入环后，又经过 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

2. 经过 x 秒，快指针停留在距离环入口距离为 b 的位置处，所以得出以下结论

b = (q * x - m) mod (n)  ------------- 推论2
// 解释：q * x 表示经过 x 秒，快指针走过的距离，再减去链表起点到环入口的距离 m 后，
// 得出在环内行走的距离，然后再模除以环的距离 mod(n)，得出停留在环中的位置，即 b

3. 同理经过 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;
    }
}

---

本文参考

为什么用快慢指针找链表的环，快指针和慢指针一定会相遇？