环形链表II

题目

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

思路分析

我们可以使用快慢指针来解决这个问题。

1、我们定义一个慢指针slow，一个快指针fast。开始的时候它们都位于链表的头部，随后，快指针每次向后移动两个位置，而慢指针每次向后移动一个位置。如果链表有环，快指针会在环中走n圈后会与慢指针在环中相遇。

2、我们假设链表头到入环口的距离为 a，从入环口到相遇点的距离为 b ，从相遇点到入环口的距离为 c，如下图:
3、当快慢指针相遇时，快指针在环中可能已经走了n圈，此时快指针走过的距离为 a + n(b + c) + b ，慢指针走过的距离为 a + b 。在任意时刻，快指针走过的距离为慢指针的 2 倍，因此，我们有如下的公式：

2(a + b) = a + n(b + c) + b

实际上我们并不关心 n 是多少，有可能是 10，也有可能是 1，因此，上述公式可以简化为： a = c 。

4、因此，当快慢指针相遇时，我们将慢指针重新指向链表头(或者定义一个新的指针指向链表头)，慢指针从链表头开始向后移动一步，此时快指针在环中从相遇点开始也是向后移动一步。

5、当快慢指针再次相遇时，它们相遇的位置就是入环点。

代码实现

var detectCycle = function (head) {
  if (!head) return null;
    // 慢指针
  let slow = head;
  // 快指针
  let fast = head;
  // 链表有环时，会继续走 while 循环
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next && fast.next.next;
    // 当快指针和慢指针在环中相遇时
    if (slow === fast) {
      // 将慢指针重新指向链表头
      slow = head;
      while (slow !== fast) {
        // 慢指针从链表头开始向后走一步
        slow = slow.next;
        // 快指针从环中的相遇点开始向后走一步
        fast = fast.next;
      }
      // 当快指针和慢指针再次相遇时，退出上面的 while 循环，此时快慢指针相遇的位置就是入环点
      return slow;
    }
  }
  return null
}