天天看點

單連結清單的環相關問題

給定一個單連結清單,隻給出頭指針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;

繼續閱讀