# 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`.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png)

```
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:**

![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png)

```
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:**

![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png)

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

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

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

```javascript
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**](https://matthung0807.blogspot.com/2020/04/floyd-cycle-detection-algorithm-floyd.html)

```javascript
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.
