链表环入口怎么找？快慢指针为什么相遇后要从头再走一次？

简化版

链表环入口可以用 Floyd 快慢指针。

先让快指针每次走 2 步、慢指针每次走 1 步；如果有环，它们一定会在环内相遇。

相遇后，让一个指针回到头节点，两个指针都每次走 1 步，再次相遇的位置就是环入口。

详细版

快慢指针检测环的原理是速度差。

如果链表有环，快指针进入环后会不断追赶慢指针，因为每轮多走 1 步，最终一定相遇。

设头节点到环入口距离为 a，入口到相遇点距离为 b，相遇点再回入口距离为 c。相遇时慢指针走了 a + b，快指针走了 a + b + k(b + c)，且快指针路程是慢指针 2 倍。

可以推出 a = k(b + c) - b，也就是从头走到入口的距离，等于从相遇点继续走到入口的距离加若干圈。

所以相遇后一个从头出发，一个从相遇点出发，同速前进，会在入口相遇。

完整版教学

一、为什么快慢指针能判断有环

链表如果没有环，快指针最终会走到 null。链表如果有环，快指针和慢指针都会进入环，之后就像两个人在环形跑道上跑步。快指针每轮比慢指针多走 1 步，因此相对距离每轮缩短 1。环长有限，最多环长轮之后一定相遇。

记忆钩子：判断有环靠“追上”，找入口靠“重走”。

二、相遇不一定是入口

很多同学误以为快慢指针第一次相遇就是环入口。实际上第一次相遇只说明有环，相遇点取决于快慢指针进入环后的相对位置。入口可能在相遇点前面，也可能相遇点离入口还差几步。

例如头部长度 a = 2，环长 4。慢指针进入环后，快指针可能已经在环里某个位置，第一次追上并不保证刚好在入口。

head -> A -> B -> C -> D -> E
              ^         |
              |_________|
入口是 B，相遇点可能是 D

三、数学推导怎么来

设：

a：头节点到环入口的距离
b：环入口到相遇点的距离
c：相遇点回到环入口的距离

相遇时慢指针走了：

a + b

快指针走了：

a + b + k(b + c)

因为快指针速度是慢指针 2 倍：

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

这说明从头到入口的距离 a，等于从相遇点到入口的距离 c 再加若干整圈。

四、为什么相遇后从头再走能到入口

相遇后，让 p1 从头节点出发，让 p2 从相遇点出发，两者每次都走 1 步。p1 走 a 步到入口。p2 走 a 步，相当于先走 c 步到入口，再绕若干整圈，最后也停在入口。

指针	起点	走 a 步后
`p1`	head	环入口
`p2`	meeting	环入口

所以第二次相遇点就是入口。

五、代码模板

实现时要先检测是否有相遇点：

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

判断节点相等要比较引用，而不是比较节点值。链表中值可能重复，只有同一个节点对象才表示相遇。

六、常见误区与追问

误区：第一次相遇点就是入口。 第一次相遇只证明有环，入口需要第二阶段定位。
误区：用节点值判断相遇。 链表节点值可能重复，必须比较节点引用。
误区：fast.next 没检查就访问 fast.next.next。 无环链表会出现空指针错误。
追问：为什么第二阶段两个指针速度都变成 1？ 因为推导得到的是距离相等，不是速度差追赶。
追问：空间 O(1) 和哈希表方案怎么取舍？ 哈希表更直观但要 O(n) 空间，Floyd 算法用数学关系换掉额外空间。

这些点能区分“会背模板”和“真的知道为什么”。

七、加强记忆

链表环入口记成两段：第一段快慢指针找相遇，靠速度差判断有环；第二段一个回头、一个留在相遇点，同速走到入口。数学上记住 a = (k - 1)环长 + c，所以头到入口和相遇点到入口在模环长意义下等价。这样就不会把第一次相遇点误认为入口。

简化版

详细版