LeetCode141——环形链表

LeetCode141——环形链表


title: LeetCode141——环形链表
date: 2019-08-18 10:04:01
updated: 2019-08-18 10:04:01
tags:

  • 算法
  • LeetCod

题目描述

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

方法一:硬破解

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

/**
 * @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)

发表评论

电子邮件地址不会被公开。 必填项已用*标注