#141. Linked List Cycle

題目描述

給你一個鏈結串列的起點head，判斷這個鏈結串列是否有一個迴圈在裡面。

如果鏈結串列中有一個迴圈，代表在訪問下一個節點時，會重複訪問到已經訪問過的節點。 pos只是用來表示連結串列的尾端節點的下一個節點位置，不會作為輸入。

如果鏈結串列中存在迴圈，回傳true，沒有則回傳false。

限制條件

節點數量在[0, 10^4]之間。
-10^5 <= 節點數值 <= 10^4。
pos只會是-1或鏈結串列長度範圍內的位置。

解題思路

HashTable

這一題是要找出有沒有迴圈存在，直覺上的解法就是把每一個訪問過的節點記錄下來，當訪問到一樣的節點時，就知道迴圈存在了。

public class Solution {
	public bool HasCycle(ListNode head) {
        var hash = new HashSet<ListNode>();
        while(head!=null){
            if(hash.Contains(head)!=true){
                hash.Add(head);
            }else{
                return true;
            }
            head=head.next;
        }
        return false;
    }
}

複雜度分析：

時間複雜度：時間複雜度為O(n)，因為一定要通過最後一個節點才知道迴圈存不存在。
空間複雜度：空間複雜度為O(n)，因為要記錄所有的節點，才知道有沒有重複訪問。

Follow-up

可以只使用到O(1)的空間嗎？

Two Pointers

如果要讓空間複雜度變成O(1)，就不能使用Hashtable記錄訪問過的節點。

我們參考龜兔賽跑的故事，假設跑道是一條直線，兔子一定比較早到終點，而如果跑道是一個圈，那麼兔子在某個時間點一定會追上烏龜。因此我們可以用兩個指標來把它當作兔子和烏龜，有迴圈存在的鏈結串列，跑得快的節點，在某個時間點上一定會和慢的節點相遇，反之則會碰到終點。

public class Solution {
	public bool HasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(slow!=null && fast !=null){
            slow = slow.next;
            if(fast.next==null) return false;
            fast = fast.next.next;
            if(slow==null || fast==null) return false;
            if(slow == fast) return true;            
        }
        return false;
    }
}

複雜度分析：

時間複雜度：在節點數量單數和雙數，並且頭尾相連的狀況下，快慢節點都會在慢節點的第n+1個時間點相遇，因此不論迴圈的節點落在哪裡，都會小於O(n)，所以取最長的時間，時間複雜度為O(n)。
空間複雜度：空間複雜度為O(1)。

學習重點

Two Pointers的應用。
Hash Table的應用。