如何判斷單連結清單是否存在環

給定一個單連結清單，隻給出頭指針h：

1、如何判斷是否存在環？

2、如何知道環的長度？

3、如何找出環的連接配接點在哪裡？

4、帶環連結清單的長度是多少？

解法：

1、對于問題1，使用追趕的方法，設定兩個指針slow、fast，從頭指針開始，每次分别前進1步、2步。如存在環，則兩者相遇；如不存在環，fast遇到NULL退出。

2、對于問題2，記錄下問題1的碰撞點p，slow、fast從該點開始，再次碰撞所走過的操作數就是環的長度s。

3、問題3：有定理：碰撞點p到連接配接點的距離=頭指針到連接配接點的距離，是以，分别從碰撞點、頭指針開始走，相遇的那個點就是連接配接點。

該定理的證明可參考：http://fayaa.com/tiku/view/7/

4、問題3中已經求出連接配接點距離頭指針的長度，加上問題2中求出的環的長度，二者之和就是帶環單連結清單的長度

原文連結：http://blog.csdn.net/liuxialong/article/details/6555850