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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

進(jìn)階：

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

解法一：標(biāo)志法

給每個(gè)已遍歷過的節(jié)點(diǎn)加標(biāo)志位，遍歷鏈表，當(dāng)出現(xiàn)下一個(gè)節(jié)點(diǎn)已被標(biāo)志時(shí)，則證明單鏈表有環(huán)

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

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

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

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

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

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

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

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

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(1)