給定一個單連結清單,隻給出頭指針h:
1、 如何判斷是否存在環?
證明:
slow首次在a點進入環路時,fast一定在環中的b點某處。設此時slow距head長為x,b點距a點長度為y,環周長為s。因為fast和slow的步差為1,是以slow前行距離為y的時候,恰好會被fast在m點追上。因為y<s,是以slow尚未完成一次周遊。
2、 如何知道環的長度?
證明:(有公式是以截圖了)
3、 如何找出環的連接配接點在哪裡?
證明:在fast和slow第一次相遇的時候,假定slow走了n步驟,環路的入口是在x步的時候經過的,那麼有
slow走的路徑: x+y = n; y為fast和slow相交點m距離環路入口的距離
fast走的路徑: x+y+k*s = 2*n; s為環路的周長,k是整數
是以得出 n = k*s;
顯然,如果從x+y點開始,slow再走n步的話,還可以回到x+y這個點(繞了k圈)
同時另一個指針temp從頭開始走的話,經過n步,也會達到x+y這點
兩者都減去y步,可知兩者走x步必然會在環路的入口點處相遇
4、帶環連結清單的長度是多少?
證明:總長度 = s + x;