如何判斷鏈表中是否有環並找出環的入口位置
前言
前面我們分析鏈表的時候提了到有一種循環鏈表，那麼假如現在給定一個單向鏈表的頭節點，如何判斷這個鏈表是否存在環？假如這個鏈表存在環，又該如何判斷環的入口位置呢？
如何判斷鏈表存在環
這道題在 leetcode 的第 142 題以及《劍指 offer》 上的第 22 題均由提到，是一個比較有意思的題目。
對於判斷單向鏈表中是否存在環這個問題，我們可以先思考一下，如果存在環，那麼當前鏈表會有什麼特點？
存在環就說明鏈表的尾節點不是指向 null，而是指向了鏈表中的另一個節點，只有這樣才會構成環，如下圖所示就是一個存在環的單向鏈表：
哈希法
假如說這個演算法不限制空間複雜度的話，也就是說允許我們在計算過程中申請額外的空間，那麼我們可以直接使用哈希表來處理。
具體的做法就是直接遍歷鏈表，並且判斷當前節點是否存在於哈希表中，如果存在，那就說明當前鏈表存在環，如果不存在，那麼我們就將當前鏈表節點存入哈希表中，並繼續往後遍歷，直到發生哈希碰撞為止。如果存在環，那麼就一定會發生哈希碰撞，如果不存在環，那麼就一定有一個節點的 next 指針指向 null，所以循環也會終止。
public static boolean isCircleByHash(ListNode head){
if (null == head){
return false;
}
Set<ListNode> set = new HashSet<>();//定義哈希集合
while (null != head){
if (set.contains(head)){//存在說明有環
return true;
}
set.add(head);
head = head.next;
}
return false;
}
快慢雙指針法
上面的介紹的哈希判斷法額外申請了空間來存儲，所以上面演算法的空間複雜度是 O(n)，那麼有沒有空間複雜度是 O(1) 的方法來判斷當前鏈表是否存在環呢？
我們設想一下這麼個場景，比如說有兩個人在圓形跑道上跑步，一個人一秒鐘跑一米，另一個人一秒鐘跑兩米，然後他們兩同時開始並且一直跑，那麼他們會不會相遇呢？
答案是只要體力允許，他們兩一定會在某一個點相遇；相反，如果是直線跑道，那麼他們就不可能相遇。所以我們可以將這個思想利用起來，這就是快慢雙指針法。
快慢雙指針法主要步驟為：定義兩個指針，一個 slow 指針，一次走一步；另一個 fast 指針，一次走兩步。如果可以在某一個點滿足 slow=fast，那麼就說明存在環，否則 fast 指針必然先到到終點。
public static boolean isCircleByTwoPoint(ListNode head){
if (null == head || null == head.next){
return false;
}
ListNode slow = head;
ListNode fast = head;
while (null != fast && null != fast.next){//注意這個條件，要防止空指針
slow = slow.next;//slow 指針一次一步
fast = fast.next.next;//fast指針一次兩步
if (slow == fast){
return true;
}
}
return false;
}
如何判斷鏈表中環的位置
環中的位置，用文中開頭的環形鏈表來說，就是節點 2，所以假如需要我們尋找這個環的入口位置，那麼該如何查找呢？
大家可能很容易想到，我們上面的哈希法判斷是否存在環的同時其實也能找到環的位置，那麼現在如果我們不利用哈希法又該如何尋找環的位置呢？
利用雙指針法可行嗎？如果直接利用上面的快慢雙指針法是行不通的，因為快慢指針相遇的位置不一定就是環的入口。
那麼該如何解決這個問題呢？答案還是要使用雙指針，但是除了雙指針之外，還需要再引入一個指針（當然，也可以復用原來的快慢指針）。
為什麼快指針只走 2 步
首先我們來分析一下上面的快慢雙指針判斷是否存在環的方法中，為什麼快指針只走 2 步，而不是 3 步，4 步，甚至更多呢？
回答這個問題之前，我們先來看看假如快指針走 3 步會有什麼問題？我們還是以文中開頭的環形鏈表為例子，當第一次 fast 走了 3 步，slow 走 1 步之後，快慢指針位置如下圖所示：
這時候 fast 繼續走 3 步，而 slow 繼續走 1 步，快慢指針位置如下圖所示：
我們發現，快指針超過了慢指針，又跑到前面去了，當然， 最終他們還是會相遇，但是這會導致一個問題，那就是當快慢指針相遇時，我們無法知道快指針在環形裡面走了多少圈，也無法知道慢指針在環形裡面走了多少圈，這會導致很難推斷環的入口位置。
而如果快指針走 2 步呢？那麼當慢指針也入環之後，每走一次，慢指針都會和快指針拉開 1 步距離；而反過來想，相當於是快指針每次都在以縮短 1 步的距離來追趕 slow 指針，因為每次只縮短 1 步，所以快慢指針一定不會出現錯過相遇點的情況。
快指針任何時候走的距離一定為慢指針的 2 倍
fast 指針在任何時候走的距離一定是 slow 指針的 2 倍，這個結論我想大家都沒什麼疑問，知道了這個結論之後，我們再來看一下下面這幅圖：
上圖中以節點為劃分，有三段鏈表，a，b，c 分別表示三段的距離，我們假設當快慢指針相遇的時候，快指針已經在環中走了 n 圈，那麼就可以得到快指針走過的距離為：a+n*(b+c)+b，而慢指針走過的距離為 a+b，根據快指針走的路程一定是慢指針的兩倍，可以得到如下等式：
a+n*(b+c)+b = 2*(a+b)，最終經過轉換，得到 a=(n-1)*(b+c) + c。
到這裡可能有人會有疑問，快慢指針相遇的時候，為什麼慢指針一定沒有走完一圈呢？如果慢指針也走了 m 圈，那麼慢指針走過的距離就是 a+m*(b+c)+b 了，但是這其實是不可能的。
為什麼快慢指針相遇時慢指針沒有走完一圈
我們假設這個環的長度為 x，那麼當 slow 指針走完一圈時，需要走 x 步，而當 slow 指針走完 x 步，fast 指針已經走了 2x 步了，也就是走了兩圈了，那麼他們一定在某一個點相遇過了（因為他們不可能錯過相遇點），所以當快慢指針第一次相遇時，慢指針是不可能走完一圈的。
利用第三個指針找到環的位置
繼續回到上面的等式：a=(n-1)*(b+c) + c，然後我們可以發現，其實 b+c 正好等於環的長度，也就是說：從鏈表頭部到入環的距離（a）恰好等於從相遇點到入環點的距離（c）再加上 n-1 圈個環的長度。
這時候就有個有趣的現象了，如果 slow 和 fast 相遇了，那麼這時候我們再定義一個指針指向鏈表起點，一次走一步，slow 指針也同步繼續往後走，那麼這兩個指針就一定會在鏈表的入口位置相遇。
public static ListNode findCyclePosition(ListNode head){
if (null == head || null == head.next){
return null;
}
ListNode slow = head;
ListNode fast = head;
while (null != fast && null != fast.next){
slow = slow.next;
fast = fast.next.next;
if (slow == fast){//快慢指針相遇時
ListNode ptr = head;//定義一個新指針
while (ptr != slow){
ptr = ptr.next;
slow = slow.next;
}
return ptr;//返迴環的入口位置
}
}
return null;
}
總結
本文主要講述了利用哈希法和雙指針法來判斷一個單向鏈表是否存在環，而最後判斷環的位置時，則需要利用快慢指針相遇後的特性來定義第三個指針，從而找到入口位置，其實找到環的位置程式碼不難，關鍵是推理的過程需要去理解。
