一 目的
- 定理推論證明
二 定理推論證明
image.png
上述變量名稱解釋
P1：鏈表的起點(diǎn)
D：鏈表的環(huán)入口（假設(shè)鏈表有環(huán)）
P2：快慢指針相遇的位置
X：鏈表起點(diǎn) P1 到環(huán)入口 D 的距離
Y：鏈表環(huán)入口 D 到相遇節(jié)點(diǎn) P2 的距離
Z：快慢指針相遇點(diǎn) P2 到環(huán)入口 D的距離
C：鏈表環(huán)的距離，即 y + z
開(kāi)始證明
假設(shè)快慢指針相遇時(shí)，快指針在環(huán)內(nèi)走了m圈，慢指針在環(huán)內(nèi)走了n圈，則有如下公式
- 快指針總共走的距離為
x + y + m * c
- 慢指針總共走的距離為
x + y + n * c
假設(shè)快指針每次走2步火本，慢指針每次走1步，則快指針走過(guò)的距離是慢指針走過(guò)距離的2倍
(x + y + m * c) = 2(x + y + n * c) 結(jié)論1
又因?yàn)榄h(huán)長(zhǎng)為c = z + y蓄喇，所以得出下面結(jié)論
(x + y + m * c) = 2(x + y + n * c)
-> c(m - 2n) = x + y
-> c(m - 2n) = x + c - z
-> x = mc - 2nc - c + z
-> x = (m - 2n - 1) * c + z 結(jié)論2
image.png
入上圖所知发侵，
- 假設(shè) 一個(gè)指針
point1從起點(diǎn)出發(fā)，走了(m-2n-1)*c步到達(dá)了P1位置妆偏。 - 另外一個(gè)指針
point2從相遇點(diǎn)P2開(kāi)始出發(fā)刃鳄，也走了(m-2n-1)*c步，最終還是停留在P1的位置（相當(dāng)于繞環(huán)走了c圈而已）钱骂。 - 這個(gè)時(shí)候叔锐，第一個(gè)指針
point1距離環(huán)入口的距離是z（由結(jié)論2得知），第二個(gè)指針point2距離環(huán)入口距離是z（之前的假設(shè)）见秽，所以兩個(gè)指針再同時(shí)走z步愉烙，就會(huì)在環(huán)入口D處相遇
結(jié)論
要想知道環(huán)入口位置，只需先使用快慢指針解取，在環(huán)內(nèi)找到相遇點(diǎn)P2步责，然后再讓兩個(gè)指針，一個(gè)從起點(diǎn)開(kāi)始出發(fā)禀苦，一個(gè)從相遇點(diǎn)P2開(kāi)始出發(fā)蔓肯，每次走一步，最終相遇的地方振乏，即為環(huán)入口D蔗包，走過(guò)的距離，也就是環(huán)入口的距離X慧邮，定理推論完畢调限。
