1.6 如何檢測一個較大的單鏈表是否有環

【出自ALBB筆試題】

難度系數：★★★★☆

被考察系數：★★★★★

題目描述：

單鏈表有環指的是單鏈表中某個結點的next域指向鏈表中在它之前的某一個結點，這樣在鏈表的尾部形成一個環形結構。如何判斷單鏈表是否有環存在？

分析與解答：

方法一：蠻力法

定義一個HashSet 用來存放結點的引用，并將其初始化為空，從鏈表的頭結點開始向后遍歷，每遍歷到一個結點就判斷HashSet中是否有這個結點的引用。如果沒有，說明這個結點是第一次訪問，還沒有形成環，那么將這個結點的引用添加到HashSet中去。如果在HashSet中找到了同樣的結點，那么說明這個結點已經被訪問過了，于是就形成了環。這種方法的時間復雜度為O（N），空間復雜度也為O（N）。

方法二：快慢指針遍歷法

定義兩個指針fast（快）與slow（慢），兩者的初始值都指向鏈表頭，指針slow每次前進一步，指針fast每次前進兩步。兩個指針同時向前移動，快指針每移動一次都要跟慢指針比較，如果快指針等于慢指針，就證明這個鏈表是帶環的單向鏈表，否則證明這個鏈表是不帶環的循環鏈表。實現代碼見后面引申部分。

引申：如果鏈表存在環，那么如何找出環的入口點？

分析與解答：

當鏈表有環時，如果知道環的入口點，那么在需要遍歷鏈表或釋放鏈表所占的空間時方法將會非常簡單，下面主要介紹查找鏈表環入口點的思路。

如果單鏈表有環，那么按照上述方法二的思路，當走得快的指針fast與走得慢的指針slow相遇時，slow指針肯定沒有遍歷完鏈表，而fast指針已經在環內循環了n圈（1≤n）。如果slow指針走了s步，則fast指針走了2s步（fast步數還等于s 加上在環上多轉的n圈），假設環長為r，則滿足如下關系表達式：

由此可以得到：s=nr

設整個鏈表長為L，入口環與相遇點距離為x，起點到環入口點的距離為a。則滿足如下關系表達式：

（L-a-x）為相遇點到環入口點的距離，從鏈表頭到環入口點的距離=（n-1）*環長+相遇點到環入口點的長度，于是從鏈表頭與相遇點分別設一個指針，每次各走一步，兩個指針必定相遇，且相遇的第一點為環入口點。實現代碼如下：

程序的運行結果為

運行結果分析：

示例代碼中給出的鏈表為1→2→3→4→5→6→7→3（3實際代表鏈表第三個結點）。因此， isLoop函數返回的結果為兩個指針相遇的結點，所以鏈表有環，通過函數FindLoopNode可以獲取到環的入口點為3。

算法性能分析：

這種方法只需要對鏈表進行一次遍歷，因此，時間復雜度為O（N）。另外，由于只需要幾個指針變量來保存結點的地址信息，因此，空間復雜度為O（1）。