如何判断链表有环并找到入环节点？快慢指针为什么有效？

知识点详解：快慢指针为什么能够找到环入口？

第一次相遇，证明链表有环

假设链表尾部的 next 错误地连回中间某个节点。这时，从头沿着 next 一直走，就不会到达 null。

慢指针每轮走一步，快指针每轮走两步。如果链表无环，快指针会到达末尾。因此，移动前必须检查 fast 和 fast.next，避免访问空节点。

如果链表有环，两个指针都会进入环。此后快指针相对慢指针每轮多走一步。可以把环看成有限个位置：相对距离每轮变化一个位置，最终必然变为零。

这个结论依赖于“一步和两步”的步长关系。不要随意把速度改成其他值，然后照搬后面的入口定位方法。

第二次相遇，为什么恰好在入口？

设头节点到入口的距离为 a，入口到第一次相遇点的环内距离为 b，环长为 L。

慢指针第一次相遇时，总共走了 a + b + kL 步；快指针走的距离是它的两倍。两者在同一位置，因此距离差是整圈长度，得到 a + b 是 L 的整数倍。

于是，a 与 -b 模 L 相同。也就是说，从相遇点再往前走 a 步，会回到入口。

让一个指针从头走 a 步，它也到入口；让另一个从相遇点走同样的 a 步，恰好也到入口。头到入口之前没有环内节点，所以两者不会提前在这段上相遇。

注意，“相遇点到入口距离等于 a”是容易误导的说法。a 可能包含多圈，准确关系是模环长相同。

图：入口定位，靠的是模环长关系。

代码分成两阶段，别把判断和定位混起来

type ListNode = { value: number; next: ListNode | null };
function cycleEntry(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      let p = head;
      while (p !== slow) {
        p = p!.next;
        slow = slow!.next;
      }
      return p;
    }
  }
  return null;
}

class ListNode:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

def cycle_entry(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            p = head
            while p is not slow:
                p, slow = p.next, slow.next
            return p
    return None

题目条件可以核对 环形链表 II。这里比较引用或身份，两个节点的 value 相同并不代表它们是同一个节点。

面试官继续追问

为什么时间复杂度不是 O(n²)？

到达环之前需要线性步数；进入环后，相对距离最多再变化一圈就相遇。第二阶段也是线性步数。两个阶段相加仍为 O(n)。

只有一个节点，指向自己呢？

同样成立。第一次移动后两个指针就相遇，入口就是这个节点。空链表和单节点无环则直接返回空。

用 Set 记录访问节点不更容易吗？

更容易解释，也能直接找到第一次重复访问的节点。但额外空间是 O(n)。面试要根据空间要求选择，而不是把 Set 方案说成错误。

面试速记卡

• 判环：慢走一步、快走两步，在环内比较节点身份。
• 找入口：一个回头，另一个留在相遇点，随后同步走一步。
• 距离依据：a + b 是环长的整数倍。
• 复杂度：O(n) 时间，O(1) 额外空间。
• 边界：空链表、单节点、自环都要检查。