【鏈表】若單鏈表存在環(huán)，如何找到環(huán)的入口點(diǎn)？更簡(jiǎn)單的證明方法是考慮從第一個(gè)節(jié)點(diǎn)開始向下的順序。當(dāng)單鏈表中的節(jié)點(diǎn)數(shù)不超過n時(shí)，它要么在有限步中結(jié)束，要么在有限步中存在重復(fù)節(jié)點(diǎn)。因?yàn)閱捂湵碇械南乱粋€(gè)節(jié)點(diǎn)是

【鏈表】若單鏈表存在環(huán)，如何找到環(huán)的入口點(diǎn)？

更簡(jiǎn)單的證明方法是考慮從第一個(gè)節(jié)點(diǎn)開始向下的順序。當(dāng)單鏈表中的節(jié)點(diǎn)數(shù)不超過n時(shí)，它要么在有限步中結(jié)束，要么在有限步中存在重復(fù)節(jié)點(diǎn)。因?yàn)閱捂湵碇械南乱粋€(gè)節(jié)點(diǎn)是唯一的，所以序列有一個(gè)固定的周期。當(dāng)單鏈表不循環(huán)時(shí)，快指針和慢指針顯然不會(huì)相遇，只考慮循環(huán)。

讓序列為a[n]，從a[i]開始，對(duì)于任何M>=i，有一個(gè)[M T]=a[M]，其中T>=1。我們只需要證明k的存在性，使得a[2K]=a[k]。取任意u，使ut>=I，k=ut，然后a[2ut]=a[ut]=a[ut（u-1）t]=。。。=a[ut]，即a[2K]=a[k]。證明了這一命題