【面試經典題】判斷鏈表是否有環| 8月更文挑戰

語言: CN / TW / HK

這是我參與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 ;

} ```

22222.png

如上圖所示

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

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

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