LeetCode141——环形链表

题目描述

给定一个链表，如何判断链表中是否有环。

方法一：硬破解

循环一定次数，或者循环一定的时间，还没有出来的就是进入到环里了，至于循环几次或者循环多久，有空的朋友可以慢慢调这个参数。🙂🙂🙂

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let now = head
    let t = 0
    while(now) {
        if (t > 10000) return true
        now = now.next
        t += 1
    }
    return false
};

方法二：哈希表

我们可以用一个 set 存下之前访问过的节点，如果再次访问了这个节点，则有环。

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    const set = new Set()
    let now = head
    while(now) {
        if (set.has(now)) return true
        set.add(now)
        now = now.next
    }
    return false
};

时间复杂度：O(n)
空间复制读：O(n)

方法三：龟兔赛跑

有两个指针，一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步。如果链表有环，则两个指针最终将会相遇。如果没有环，则永远不会相遇。

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let fast = slow = head
    while(fast && slow && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if (fast === slow) return true
    }
    return false
};

时间复杂度：O(n)
空间复杂度：O(1)