前戲

怎樣判斷單鏈表有環？這個問題應該是面試中經常會被問到的問題，例如下圖所示：

看到這個問題，你們想到了什麼方法呢？歡迎在評論區留言！

方法1：

按照我們文章循序漸進的特點，我們先來看個簡單的，也是最容易想到的方法:首先從頭結點A開始依次遍歷，每次遍歷節點依次跟之前遍歷過的節點進行比較。如果發現存在相同的節點。說明已經遍歷過了，就存在有環。那麼通過簡單的計算它的時間複雜度O(n^2),空間複雜度基本是可以認為是O(1)，因為基本沒有消耗內存。當然這種方法是最原始的，當然有比這個好點的算法。我們往下看

方法2：

按照上面的方法1的啟示，是不是可以將遍歷過的節點存儲在STL::hash_set容器中，這樣遍歷到下一個節點時，可以通過用新節點和容器中的存儲節點進行比較，如果存在相同節點。則說明是鏈表有環。這個方法在時間複雜度為O(n)，是對方法1的改進。但在空間複雜度上為O(n)，沒有方法1做得好。那麼有童鞋會問，那還有沒有更好的辦法呢？可以將空間複雜度降下來？答案是：有。我們往下看

方法3：

首先創建兩個指針P1，P2，同時指向鏈表的頭節點。在循環體中（P2和P1為空跳出循環），P1指針每次向下移動一個節點（P2->next）。而P2每次向下移動兩個節點（P2->next->next）。判斷P1和P2指針是否相等即可。時間複雜度為O(n),而空間複雜度跟方法1一致為O(1)。各位童鞋理解了嗎？沒理解的給段很簡單的代碼看下：

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 ;
}

可能有童鞋又會問了：為什麼有環他們就會碰到一起？

我這裡可以用簡單的例子解釋下，嚴謹的證明需要比較長的篇幅，不展開。有環的判斷，就像我們在田徑賽道上跑1萬米，大家是不是經常看到跑的慢的童鞋被跑的快的套圈呢，其實道理是一樣的。

好了，本期的文章就到這裡，歡迎大家的支持，咱們下期再見!