链表环：检测与入口查找

一、面试常考点

1. 判环

Floyd 判圈法：快慢指针是否相遇。

2. 找环入口

相遇后一个指针回头，两指针同速前进再次相遇即入口。

二、细节介绍

1. 数学关系

设头到入口为 a，入口到相遇为 b，环长 c，可推出从头与相遇点同速前进会在入口相遇。

三、示例代码

function detectCycle(head) {
  let slow = head
  let 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
}

四、常用应用场景

1. 循环依赖检测

链式结构中的闭环识别。

2. 迭代器死循环排查

检测引用结构是否形成环。