一 目的

• 定理推論證明

二 定理推論證明

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

開始證明

假設(shè)快慢指針相遇時(shí)，快指針在環(huán)內(nèi)走了m圈，慢指針在環(huán)內(nèi)走了n圈，則有如下公式

• 快指針總共走的距離為

 x + y + m * c

• 慢指針總共走的距離為

x + y + n * c

假設(shè)快指針每次走2步，慢指針每次走1步，則快指針走過的距離是慢指針走過距離的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

入上圖所知，

1. 假設(shè) 一個(gè)指針point1從起點(diǎn)出發(fā)，走了(m-2n-1)*c步到達(dá)了P1位置。
2. 另外一個(gè)指針point2從相遇點(diǎn)P2開始出發(fā)，也走了(m-2n-1)*c步，最終還是停留在P1的位置（相當(dāng)于繞環(huán)走了c圈而已）。
3. 這個(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)開始出發(fā)，一個(gè)從相遇點(diǎn)P2開始出發(fā)，每次走一步，最終相遇的地方，即為環(huán)入口D，走過的距離，也就是環(huán)入口的距離X，定理推論完畢。