环形链表怎样找到入环点？为什么相遇后从头再走就能找到？

简答

环形链表就是链表尾部的 next 没有指向 null，而是指回了前面某个节点，一直往后走永远走不完。题目要返回环开始的那个节点，也就是入环点，没有环就返回 null，而且不能修改链表。

做法分两步。第一步用快慢指针判环：慢指针每次走一步，快指针每次走两步，有环时快指针进了环就在里面绕，每走一轮都比慢指针多走一步，迟早追上。第二步，相遇后把一个指针放回头节点，两个指针都改成每次走一步，再次相遇的节点就是入环点。

第二步成立是因为一个等式。设头到入环点距离为 a，入环点到相遇点为 b，环长为 c。快指针走的路是慢指针的两倍，推出 a 等于相遇点再往前走 c − b 步回到入环点，再加上若干整圈。所以两个指针同速走 a 步，正好在入环点碰头。

这样只要 O(n) 时间和 O(1) 额外空间。用 Set 记录走过的节点也能做，第一个重复出现的节点就是入环点，但要 O(n) 额外空间。要注意循环条件写 fast && fast.next，比较的是节点引用，不是节点的值。

先判环，再找入环点

detectCycle 前半段就是判环，后半段把 slow 放回头节点。看第二个循环里两个指针都只走一步。

function fromArray(values, pos) {
  const nodes = values.map((value) => ({ value, next: null }));
  nodes.forEach((node, i) => (node.next = nodes[i + 1] ?? null));
  // pos 和 LeetCode 一样表示尾节点连回的下标，-1 表示无环
  if (pos >= 0) nodes[nodes.length - 1].next = nodes[pos];
  return nodes[0] ?? null;
}

function detectCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }
  return null;
}

console.log(detectCycle(fromArray([3, 2, 0, -4], 1)).value); // 2
console.log(detectCycle(fromArray([1, 2], 0)).value); // 1
console.log(detectCycle(fromArray([1], -1))); // null
console.log(detectCycle(fromArray([], -1))); // null

const sameValues = fromArray([7, 7, 7, 7], 2);
console.log(detectCycle(sameValues) === sameValues.next.next); // true

第一个例子里尾节点 -4 连回下标 1，所以入环点是值为 2 的节点。最后一个例子所有节点的值都是 7，看值分不出是哪个节点，所以用 === 比较返回的引用是不是第三个节点。

为什么一定会相遇，快指针不会跳过慢指针吗？两个指针都进环以后，每走一轮，快指针和慢指针之间的距离就缩短 1。距离一步步减到 0，中间不会跳过，所以必然相遇。而且慢指针进环后走不满一圈就会被追上，因为快指针追它最多要追一圈的距离。

为什么相遇后从头走能到入环点

设头节点到入环点要走 a 步，入环点到相遇点要走 b 步，环一共 c 个节点。相遇时慢指针走了 a + b 步。快指针在环里多绕了 k 圈（k ≥ 1），走了 a + b + kc 步。快指针的步数是慢指针的两倍：

2(a + b) = a + b + kc
a + b = kc
a = kc - b = (k - 1)c + (c - b)

最后一行要这样读：从相遇点再往前走 c − b 步，正好回到入环点；再多绕 k − 1 圈，还是停在入环点。所以一个指针从头走 a 步到达入环点时，另一个从相遇点同样走 a 步，也恰好在入环点。两者第一次相同的位置就是入环点，因为在此之前一个还在环外，另一个在环里，不可能重合。

a = 0 的情况也成立，比如第二个例子尾节点连回头节点，相遇后 slow 回到头，它本来就是入环点，第二个循环一次都不执行。

常见追问

用 Set 做有什么不同？

一路往后走，把每个节点放进 Set，第一次碰到已经在 Set 里的节点就是入环点，走到 null 就说明无环。写法更直白，时间也是 O(n)，但额外空间是 O(n)。Set 按引用区分对象，所以值重复的节点不会误判。

怎么求环的长度？

快慢指针相遇后，让其中一个继续走，同时计数，再回到相遇点时走过的步数就是环长 c。

只判断有没有环的写法在哪里？

见《怎样反转链表、判断链表有环？》，那里只用到第一步，相遇就返回 true。