141. Linked List Cycle

Leetcode

https://leetcode.com/problems/linked-list-cycle/

題目

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

解答

• 方法一

有點偷吃步的感覺，由於 js 原生的 Map 鍵值 key 可以是 object 的形式，所以遍歷時就把每個節點存到 key 中，判斷如果 key 有出現過，那就代表這個鏈錶是有循環的

var hasCycle = function (head) {
    const map = new Map();

    while (head) {
        if (map.has(head)) {
            return true;
        } else {
            map.set(head, true);
            head = head.next;
        }
    }

    return false;
};

Runtime: 171 ms, faster than 5.14% of JavaScript online submissions for Linked List Cycle.

Memory Usage: 42.9 MB, less than 5.70% of JavaScript online submissions for Linked List Cycle.

• 方法二

Floyd's Cycle Finding Algorithm

var hasCycle = function (head) {
    if (!head) {
        return false;
    }

    let slow = head;
    let fast = head.next;

    while (slow !== fast) {
        // 如果 fast 已經走到終點，代表沒有循環
        if (fast === null || fast.next === null) {
            return false;
        }

        slow = slow.next;
        fast = fast.next.next;
    }

    return true;
};

Runtime: 80 ms, faster than 81.85% of JavaScript online submissions for Linked List Cycle.

Memory Usage: 41.3 MB, less than 72.11% of JavaScript online submissions for Linked List Cycle.