【LeetCode】環路檢測（連結清單）

連結清單回環問題：

給定一個連結清單，如果它是有環連結清單，實作一個算法傳回環路的開頭節點。

如果連結清單中有某個節點，可以通過連續跟蹤 next 指針再次到達，則連結清單中存在環。 為了表示給定連結清單中的環，我們使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該連結清單中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了辨別連結清單的實際情況。

示例 1：

輸入：head = [3,2,0,-4], pos = 1

輸出：tail connects to node index 1

解釋：連結清單中有一個環，其尾部連接配接到第二個節點。

哈希表解法：

從前到後依次的去周遊并加入到哈希表中，第一個出現重複的結點就是這個環的開頭結點！

public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<ListNode>();
		
		while(head!=null) {
			if(set.contains(head))
				return head;
			set.add(head);
			head = head.next;
		}
		
		return null;
    }
           

快慢指針解法：

思路與算法

我們使用兩個指針，fast 與slow。它們起始都位于連結清單的頭部。随後，slow 指針每次向後移動一個位置，而 fast 指針向後移動兩個位置。如果連結清單中存在環，則fast 指針最終将再次與slow 指針在環中相遇。

如下圖所示，設連結清單中環外部分的長度為 a。slow 指針進入環後，又走了 b 的距離與 fast 相遇。此時，fast 指針已經走完了環的 n 圈，是以它走過的總距離為 a+n(b+c)+b=a+(n+1)b+nc。

根據題意，任意時刻，fast 指針走過的距離都為slow 指針的 2 倍。是以：

a+(n+1)b+nc= 2(a+b) ==> a=c+(n-1)(b+c) ==> a = c

通過上面的等式可以得出結論：當slow與fast相遇時，a這個距離是等于c這個距離的，是以這時定義一個pre指針指向連結清單的表頭，pre與slow都一步一步的走，在pre與slow相遇時，它們指向的結點就是環的開頭結點了！

public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
		ListNode fast = head;
		
		while(true) {
			if(fast==null||fast.next==null)
				return null;
			slow = slow.next;
			fast = fast.next.next;
			if(slow==fast)
				break;
		}
		
		ListNode pre = head;
		
		while(pre!=slow) {
			pre = pre.next;
			slow = slow.next;
		}
		
		return pre;
    }
           

第二種快慢指針的解法，如果光看的話太抽象了，找不到什麼關系，通過數學邏輯去分析把這些抽象的東西用變量代替然後寫出等式，将這些抽象的關系用數學邏輯關聯到了一起，答案一下就清晰了。