142. Linked List Cycle II 快慢指针证明与分析

[SHISME]

leetcode 上这道题如果有map的方式可以很容易的解决，但是如果我们想用快慢指针的方式解决这道题，虽然从代码的层面上来看任然很简单，但是如果你想严谨的去证明为什么这样可以就不太容易了，看了很多人的分析，但是感觉证明过程都不太严谨，所以这里写一篇严谨的证明过程.

证明

快指针的速度是慢指针的两倍，首先我们假设是有环的，我们需要先假设几个变量

• 出发点到环进入点, AB长度为: x
• 快指针和慢指针相遇的位置距环进入点，BC长度为: y
• 圆环长度为: l

当快慢相遇时，假设快指针在圆环内跑了 n 圈，慢指针跑了 m圈.

1. 此时慢指针走过的距离为 x + l * n + y, 快指针走过的距离为 x + l * m + y
2. 因为快指针的速度是慢指针的两倍，所以2(x + l * n + y) = x + l * m + y,
3. 推导得 x + y = l(m - 2n), 因为 m 和 n都为整数,所以 m -2n也为整数,
4. 公式可以看作是 x + y = kl, k 为整数, 推导得 x = kl - y
5. 相遇点到圆环点的距离BC为 y, 如果从相遇点走多 x步, 则会到距离圆环切入点kl的位置，刚好就是圆环的切入点
6. 所以当快慢指针相遇的时候，我们用一个指针以相同的速度从链表头出发，慢指针继续跑，当两个指针指向相同的时候即为圆环切入点

[SHISME]

js 代码实现

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const detectCycle = function(head) {
  let quick = head;
  let slow = head;
  while (quick) {
      quick = quick.next ? quick.next.next : null;
      slow = slow.next;
      if (quick === slow && quick !== null) {
          break;
      }
  }
  if (!quick) {
      return null
  }
  quick = head;
  while (quick !== slow) {
      quick = quick.next;
      slow = slow.next;
  }
  return quick;
};