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.

Example 1:

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:

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:

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

Constraints:

• The number of the nodes in the list is in the range [0, 104].

• -105 <= Node.val <= 105

• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

这是一道定势题。当然，如果我们用空间换时间是非常简单的：单纯记录所有的节点，一旦发现重复立刻返回即可。不过这个问题有一个经典的快慢指针解法，思路如下：

快指针每次走两格，慢指针每次走一格，如果两者重复，则说明有环。此时，快指针比慢指针多走了n个环的长度的距离。同时，我们知道快指针速度是慢指针两倍，走的距离也就是慢指针两倍。

设 L1 为起始点到环入口的距离，L2 为环入口到相遇点的距离，C为环的周长，则有：

L1+L2+NC = 2(L1+L2)

演变得

L1 = (N-1)C + (C-L2)

由此可得：如果我们把快指针移回首个节点，每次只走一格，它一定会和慢指针相遇，相遇的位置即是入口。

注意：在把快指针移动到起始点后必须立刻进行判定，此时 L1=0, N=1, C=L2，其实也就是整个链表头尾相连的情况。如果等动了之后再进行判定显然错判这种情况（因为快慢指针此时将判到移动后的点上）。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let slow = head, fast = head, meet = false
    
    while(fast && fast.next && fast.next.next) {
        fast = meet ? fast.next : fast.next.next
        slow = slow.next

        if (fast === slow) {
            if (meet || fast === head) {
                return fast
            }
            meet = true
            fast = head
        }
    }
    
    return null
};