一 目的

本文目的有2點
第一，如果快慢指針相遇，證明鏈表有環(huán)。這個理論是如何推理證明出來的？
第二，代碼實現(xiàn)快慢指針相遇，證明鏈表有環(huán)。

二 快慢指針相遇，證明鏈表有環(huán)，理論證明

image.png

下面是針對圖中變量做一些解釋說明

1.鏈表起點，假設(shè)為 head
2.假設(shè)鏈表有環(huán)，環(huán)入口假設(shè)為 entry
3.起點到環(huán)入口的距離假設(shè)為 m
4.慢指針一秒走 s 步
5.快指針一秒走 q 步
6.慢指針第一次進(jìn)入環(huán)后距離環(huán)入口的距離假設(shè)為 a
7.當(dāng)慢指針第一次進(jìn)入環(huán)后，快指針距離環(huán)入口的距離為 b
8.經(jīng)過 x 秒，慢指針第一次進(jìn)入環(huán)
9.鏈表環(huán)長為 n

接下來開始理論證明推導(dǎo)

1. 假設(shè)當(dāng)慢指針第一次進(jìn)入環(huán)后，又經(jīng)過 y 秒后，兩指針相遇在某個節(jié)點，所以得出下面這個結(jié)論

// (b + q * y) 表示經(jīng)過y秒后，快指針距離環(huán)入口的距離（假設(shè)沒有環(huán)，一條直線，一直往前走）
// 再 mod(n) 模上 n(鏈表環(huán)長)，計算出最終停留位置距離環(huán)入口的距離
(b + q * y) mod (n) 

// 同理下面公式表示經(jīng)過y秒后，最終慢指針停留位置距離環(huán)入口的距離
(a + s * y) mod (n)

// 因為最終兩個指針相遇，所以他們距離環(huán)入口的距離相等，所以得出
(b + q * y) mod (n)  == (a + s * y) mod (n) ------------------ 推論1

2. 經(jīng)過 x 秒，快指針停留在距離環(huán)入口距離為 b 的位置處，所以得出以下結(jié)論

b = (q * x - m) mod (n)  ------------- 推論2
// 解釋：q * x 表示經(jīng)過 x 秒，快指針走過的距離，再減去鏈表起點到環(huán)入口的距離 m 后，
// 得出在環(huán)內(nèi)行走的距離，然后再模除以環(huán)的距離 mod(n)，得出停留在環(huán)中的位置，即 b

3. 同理經(jīng)過 x 秒，慢指針停留在距離環(huán)入口距離為 a 的位置處，所以得出以下結(jié)論

a = (s * x - m) mod (n) ---------------- 推論3

4.下面由上述得到的三個推論進(jìn)行推理

由推論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
當(dāng)快指針一秒走2步，慢指針一秒走一步時，得 q - s = 1,即
(x + y) mod (n) = 0，即當(dāng) x + y 為 n 的整數(shù)倍時，可以保證 (x + y) mod (n) = 0

總結(jié)

最終得出結(jié)論 (x + y) mod (n) = 0，即肯定存在 x與y，保證 x + y為n的整數(shù)倍，使得等式 (x + y) mod (n) = 0成立，即 快慢指針相遇，證明鏈表有環(huán)結(jié)論推導(dǎo)證明成功。

三 代碼實現(xiàn)快慢指針相遇，證明鏈表有環(huán)

Leetcode題目連接地址 141. 環(huán)形鏈表

public class Solution {
  // 鏈表節(jié)點
  class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    
    // 鏈表是否有環(huán)
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slowNode = head;
        ListNode fastNode = head.next;
        // 使用快慢節(jié)點
        while (fastNode != null && fastNode.next != null) {
            if (slowNode == fastNode) {
                return true;
            }
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        return false;
    }
}

本文參考

為什么用快慢指針找鏈表的環(huán)，快指針和慢指針一定會相遇？