floyd判環算法（龜兔賽跑算法）

floyd判環算法（龜兔賽跑算法）

注意，這個算法是用來判斷一條鏈+一條環的圖，環的長度或者環與鏈的交界處的，所以此floyd非彼floyd（雖然都是一個人想出來的）。

（圖不是我的）

如果只要求環的長度的話，只要讓h和t相遇，然后再讓h跑一圈，同時計算出步數就行了。

如果要算出鏈和環的交界點呢？首先，指針h和t同時從S出發，速度一個為2，一個為1（不要在意細節）。當t走到鏈和環的交界點時，在右邊的ht的距離等于st的距離。設st的距離為x，在左邊的ht距離為y，那么環的長度就是x+y。現在讓h和t繼續走，直到m相交，那么顯然右邊的tm的距離就是y。由于環的長度是x+y，所以左邊的tm長度就為x。現在讓兩個等速的點一個在s，一個在m，同時走，就會在t碰頭，于是交界處的點就求出來了。

由于codevs又雙叒叕上不去了，所以暫時沒有題目。