快慢指针法可高效判断单链表是否有环：慢指针每次走1步、快指针每次走2步，若相遇则有环，若快指针到达null则无环；PHP实现需检查快指针及其next非空，相遇即返回true。
快慢指针法（Floyd 判圈算法）
判断单链表是否有环最经典、高效的方法是快慢指针法。核心思想是：用两个指针从头结点出发，一个每次走1步（慢指针），一个每次走2步（快指针）。如果链表有环，快指针迟早会追上慢指针；如果无环，快指针会先到达 null。
关键细节：
- 初始时两个指针都指向头结点（或慢指针=head，快指针=head->next，取决于实现习惯；但需确保快指针不为空再进入循环）
- 循环条件必须检查快指针及其 next 是否为 null，避免空指针解引用
- 相遇即说明存在环，返回 true；快指针为 null 说明已到链表尾，返回 false
PHP 实现示例
假设链表节点定义如下：
public $val;
public $next;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
?>
判断函数：
立即学习“PHP免费学习笔记（深入）”；
function hasCycle($head) {if ($head === null || $head->next === null) {
return false;
}
$slow = $head;
$fast = $head;
while ($fast !== null && $fast->next !== null) {
$slow = $slow->next;
$fast = $fast->next->next;
if ($slow === $fast) {
return true;
}
}
return false;
}
?>
为什么能保证一定相遇？
在环中，快指针比慢指针每次多走1步。设环长为 L，两指针进入环后，它们之间的距离（沿环方向）每次减少1。即使初始距离是 L−1，最多 L 步内必然重合。不会“跳过”慢指针，因为步长差是固定整数1。
扩展：找环入口点（可选）
若还需返回环的起始节点（如 LeetCode 142），可在快慢指针相遇后：
– 将一个指针重置到 head，另一个留在相遇点；
– 两指针同时每次走1步，再次相遇处即为环入口。
原理基于数学推导：设头到环入口为 a，入口到相遇点为 b，环剩余部分为 c，则有 2(a+b) = a + n(b+c) + b ⇒ a = (n−1)(b+c) + c，说明从 head 和相遇点同步出发必在入口相遇。
