【鏈表】若單鏈表存在環(huán)，如何找到環(huán)的入口點？更簡單的證明方法是考慮從第一個節(jié)點開始向下的順序。當(dāng)單鏈表中的節(jié)點數(shù)不超過n時，它要么在有限步中結(jié)束，要么在有限步中存在重復(fù)節(jié)點。因為單鏈表中的下一個節(jié)點是

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

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

讓序列為a[n]，從a[i]開始，對于任何M>=i，有一個[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]。證明了這一命題