环形链表 (opens new window)

• 难度：Easy
• 标签：

刷题思路

• [x] Hash暴力对比
• [x] 标志位法
• [ ] 快慢指针

方法 1 Hash暴力对比

• 复杂度：
  • 时间 O(N). 一次遍历
  • 空间 O(N). 每个节点都暂存直到找到.
• 结果:
  • 执行用时：92 ms, 在所有 JavaScript 提交中击败了68.23%的用户
  • 内存消耗：40.4 MB, 在所有 JavaScript 提交中击败了5.03%的用户

var hasCycle = function(head) {
    const set = new Set()
    while (head) {
        if (set.has(head)) return true
        set.add(head)
        head = head.next
    }
    return false
};

方法 2 标志位法

• 复杂度：
  • 时间 O(n)
  • 空间 O(1)
• 结果：
  • 执行用时：116 ms, 在所有 JavaScript 提交中击败了9.79%的用户
  • 内存消耗：39.7 MB, 在所有 JavaScript 提交中击败了51.46%的用户

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

方法 3 快慢指针

• 复杂度：
  • 时间 O(n)
  • 空间 O(1)
• 结果：
  • 执行用时：104 ms, 在所有 JavaScript 提交中击败了24.80%的用户
  • 内存消耗：39.8 MB, 在所有 JavaScript 提交中击败了38.70%的用户

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

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~