# 142. Linked List Cycle II

### Leetcode

<https://leetcode.com/problems/linked-list-cycle-ii/>

### 題目

Given the `head` of a linked list, return *the node where the cycle begins. If there is no cycle, return* `null`.

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 (**0-indexed**). It is `-1` if there is no cycle. **Note that** `pos` **is not passed as a parameter**.

**Do not modify** the linked list.

&#x20;

**Example 1:**

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

```
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
```

**Example 2:**

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

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

**Example 3:**

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

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

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

* **方法一**

[**Floyd's Cycle Finding Algorithm**](https://matthung0807.blogspot.com/2020/04/floyd-cycle-detection-algorithm-floyd.html)

```
var detectCycle = function(head) {
    if(!head || !head.next) return null;
    
    // slow 最初位置
    let slow = head.next;
    // fast 最初位置
    let fast = head.next.next;
    while(slow !== fast) {
        if(fast === null || fast.next === null) return null;
        slow = slow.next;
        fast = fast.next.next;
    }

    // 把 slow 放回原位，然後兩方都各以一步同步前進，碰到時即為 cycle 的起點
    slow = head;
    while(slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
};
```

Runtime: 88 ms, faster than 53.73% of JavaScript online submissions for Linked List Cycle II.

Memory Usage: 41.6 MB, less than 60.02% of JavaScript online submissions for Linked List Cycle II.
