每日算法：判斷一個單鏈表是否有環(huán)

給定一個鏈表，判斷鏈表中是否有環(huán)。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)。

進階：

你能用 O(1)（即，常量）內(nèi)存解決此問題嗎？

解法一：標志法

給每個已遍歷過的節(jié)點加標志位，遍歷鏈表，當出現(xiàn)下一個節(jié)點已被標志時，則證明單鏈表有環(huán)

let hasCycle = function(head) {
    while(head) {
        if(head.flag) return true
        head.flag = true
        head = head.next
    }
    return false
};

時間復雜度：O(n)

空間復雜度：O(n)

解法二：利用 JSON.stringify() 不能序列化含有循環(huán)引用的結(jié)構(gòu)

let hasCycle = function(head) {
    try{
        JSON.stringify(head);
        return false;
    }
    catch(err){
        return true;
    }
};

時間復雜度：O(n)

空間復雜度：O(n)

解法三：快慢指針（雙指針法）

設置快慢兩個指針，遍歷單鏈表，快指針一次走兩步，慢指針一次走一步，如果單鏈表中存在環(huán)，則快慢指針終會指向同一個節(jié)點，否則直到快指針指向 null 時，快慢指針都不可能相遇

let hasCycle = function(head) {
    if(!head || !head.next) {
        return false
    }
    let fast = head.next.next, slow = head.next
    while(fast !== slow) {
        if(!fast || !fast.next) return false
        fast = fast.next.next
        slow = slow.next
    }
    return true
};

時間復雜度：O(n)

空間復雜度：O(1)