快慢指针能检测环是因为:若有环,快慢指针必在环内相遇;若无环,快指针必先到达nullptr;数学上可证——慢指针入环时,快指针已在环中,相对速度为1,最多环长步内必相遇。

快慢指针为什么能检测环
因为如果链表有环,两个以不同速度前进的指针最终一定会在环内相遇;没环的话,快指针会先走到 nullptr。这不是概率问题,而是数学上可证明的:设环长为 L,入环前长度为 M,当慢指针刚进环时,快指针已在环内某处,之后每轮迭代两者距离减 1,最多 L 轮必相遇。
ListNode 结构和基本判断条件
标准实现依赖 next 指针是否为空。必须先检查 head 和 head->next 是否为 nullptr,否则直接解引用会崩溃:
if (!head || !head->next) return false;
常见错误是只判 head == nullptr,漏掉单节点无环但 head->next 为空的情况,导致后续 fast = fast->next->next 访问非法内存。
快慢指针初始化与循环终止条件
慢指针从 head 开始,快指针从 head->next 开始(不能都从 head 起步,否则第一次就相等,误判为有环):
立即学习“C++免费学习笔记(深入)”;
-
slow = head,fast = head->next - 循环中每次更新:
slow = slow->next,fast = fast->next->next - 终止条件是:
fast == nullptr || fast->next == nullptr(快指针走到末尾)或slow == fast(相遇)
注意:必须先判 fast 是否为空,再访问 fast->next,否则空指针解引用。
环存在时如何找入环点(额外但实用)
相遇后,把一个指针重置到 head,另一个留在相遇点,然后都每次走一步,再次相遇的位置就是入环节点。原理是:设头到入环点距离为 a,入环点到相遇点距离为 b,环剩余长度为 c,则有 2(a + b) = a + b + n(b + c),整理得 a = (n−1)(b + c) + c,即从头出发的指针走 a 步、从相遇点出发的指针走 c + 若干整圈,刚好都在入环点碰头。
这个步骤常被忽略,但调试环形链表时非常有用——比如要断开环或定位错误插入位置。


















