141. 环形链表

[Geekhyt]

原题链接

链表的基础知识可以移步这个题解，这里不再赘述。

快慢指针

1.使用快慢不同的两个指针遍历，快指针一次走两步，慢指针一次走一步。
2.如果没有环，快指针会先到达尾部，返回 false。
3.如果有环，则一定会相遇。

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

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

标记法

遍历链表，通过 flag 标记判断是否有环，如果标记存在则有环。(走过的地方插个旗子做标记)

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

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