這是我參與8月更文挑戰的第7天，活動詳情查看：8月更文挑戰

想要堅持寫點什麼，那乾脆寫一個系列吧。想想有什麼可以寫的呢？程序=算法+數據結構，可見算法的重要性。這個系列老詩力求用最簡單的語言把算法講得明明白白，由淺到深，有興趣的話，可以關注一下專欄。

上一篇文章寫了鏈表的基本操作，包括新建鏈表，插入鏈表節點，刪除鏈表節點，查詢鏈表結點等內容。 現在這一篇是講如何判斷鏈表是否有環的算法。面試中這一題目是比較常見的。

快慢指針判斷法

對於這個問題我們可以採用“快慢指針”的方法。就是有兩個指針fast和slow，開始的時候兩個指針都指向鏈表頭head，然後在每一步操作中slow向前走一步即：slow = slow->next，而fast每一步向前兩步即：fast = fast->next->next。由於fast要比slow移動的快，如果有環，fast一定會先進入環，而slow後進入環。當兩個指針都進入環之後，經過有限的操作次數之後，快慢指針是必定會相遇的。

具體代碼如下：

``` //快慢指針判斷是否有環 bool exitLoop(Node head) { Node fast, *slow ; slow = fast = head ;

while (slow != NULL && fast -> next != NULL) 
{ 
    slow = slow -> next ; 
    fast = fast -> next -> next ; 
    if (slow == fast) 
        return true ; 
} 
return false ;

} ```

如上圖所示

也就是説，slow每次向前走一步，fast向前追了兩步，因此每一步操作後fast到slow的距離縮短了1步，這樣繼續下去就會使得兩者之間的距離逐漸縮小：...、5、4、3、2、1、0 -> 相遇。又因為在同一個環中fast和slow之間的距離不會大於換的長度，因此到二者相遇的時候slow一定還沒有走完一週（或者正好走完以後，這種情況出現在開始的時候fast和slow都在環的入口處）。

想要學習更多算法問題，或者要更多項目源碼，請移步到公眾號：詩一樣的代碼。

既然進來了，原創不易。小夥伴點個贊再走唄。