一 目的
本文目的有2點(diǎn)
第一轧抗，如果快慢指針相遇恩敌，證明鏈表有環(huán)。這個(gè)理論是如何推理證明出來的横媚？
第二纠炮，代碼實(shí)現(xiàn)快慢指針相遇，證明鏈表有環(huán)灯蝴。
二 快慢指針相遇恢口，證明鏈表有環(huán)，理論證明
image.png
下面是針對圖中變量做一些解釋說明
1.鏈表起點(diǎn)穷躁，假設(shè)為 head
2.假設(shè)鏈表有環(huán)耕肩，環(huán)入口假設(shè)為 entry
3.起點(diǎn)到環(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)
- 假設(shè)當(dāng)慢指針第一次進(jìn)入環(huán)后猿诸，又經(jīng)過
y秒后，兩指針相遇在某個(gè)節(jié)點(diǎn)狡忙，所以得出下面這個(gè)結(jié)論
// (b + q * y) 表示經(jīng)過y秒后梳虽，快指針距離環(huán)入口的距離（假設(shè)沒有環(huán)，一條直線灾茁，一直往前走）
// 再 mod(n) 模上 n(鏈表環(huán)長)窜觉，計(jì)算出最終停留位置距離環(huán)入口的距離
(b + q * y) mod (n)
// 同理下面公式表示經(jīng)過y秒后是复，最終慢指針停留位置距離環(huán)入口的距離
(a + s * y) mod (n)
// 因?yàn)樽罱K兩個(gè)指針相遇，所以他們距離環(huán)入口的距離相等竖螃，所以得出
(b + q * y) mod (n) == (a + s * y) mod (n) ------------------ 推論1
- 經(jīng)過
x秒淑廊，快指針停留在距離環(huán)入口距離為b的位置處，所以得出以下結(jié)論
b = (q * x - m) mod (n) ------------- 推論2
// 解釋：q * x 表示經(jīng)過 x 秒特咆，快指針走過的距離季惩，再減去鏈表起點(diǎn)到環(huán)入口的距離 m 后，
// 得出在環(huán)內(nèi)行走的距離腻格，然后再模除以環(huán)的距離 mod(n)画拾，得出停留在環(huán)中的位置，即 b
- 同理經(jīng)過
x秒菜职，慢指針停留在距離環(huán)入口距離為a的位置處青抛，所以得出以下結(jié)論
a = (s * x - m) mod (n) ---------------- 推論3
4.下面由上述得到的三個(gè)推論進(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步酬核，慢指針一秒走一步時(shí)蜜另，得 q - s = 1,即
(x + y) mod (n) = 0，即當(dāng) x + y 為 n 的整數(shù)倍時(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)證明成功旧巾。
三 代碼實(shí)現(xiàn)快慢指針相遇耸序，證明鏈表有環(huán)
Leetcode題目連接地址 141. 環(huán)形鏈表
public class Solution {
// 鏈表節(jié)點(diǎn)
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é)點(diǎn)
while (fastNode != null && fastNode.next != null) {
if (slowNode == fastNode) {
return true;
}
slowNode = slowNode.next;
fastNode = fastNode.next.next;
}
return false;
}
}
本文參考
