快慢指针能定位环起始点是因为数学关系a=(k−1)(b+c)+c，即头节点走a步与相遇点走c步同时达入口；先Floyd判环得相遇点，再双指针同速前进至再次相遇即入口。
为什么快慢指针能定位环的起始点
快慢指针相遇只说明有环，但相遇点不等于环入口。关键在于数学关系：设头节点到环入口距离为 a，环入口到相遇点距离为 b，剩余环长为 c（即环总长 b + c）。当慢指针走了 a + b，快指针走了 a + b + k(b + c)（k ≥ 1），且快指针路程是慢指针的两倍，推导可得 a = k(b + c) - b = (k-1)(b + c) + c。这意味着：从头节点出发走 a 步，和从相遇点出发走 c 步，会同时到达环入口。
标准解法：两次双指针扫描
第一步用 floyd 判环并获取相遇点；第二步将一个指针重置到 head，另一个留在相遇点，两指针以相同速度（每次一步）前进，再次相遇处即为环入口。
- 必须先确认链表有环，否则
slow == fast为假时直接返回nullptr - 重置后两个指针都必须严格每次走 1 步，不能复用之前的快慢节奏
- 注意边界：若
head为nullptr或只有单节点，直接返回nullptr
ListNode *detectCycle(ListNode *head) {
if (!head || !head->next) return nullptr;
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (slow != fast) return nullptr; // 无环
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
容易被忽略的指针移动细节
常见错误不是算法逻辑错，而是指针初始化或移动时机不对。
- 第一次循环中，
fast必须先判fast && fast->next再移动，否则可能对空指针调用->next - 相遇后重置
slow到head，但fast保持在原相遇节点，不要重置成head或重新设为head->next - 第二次循环的条件是
slow != fast，进入循环前不相等，靠同步移动最终撞上——不能写成while (slow->next != fast->next)这类错误推导
没有额外空间，但时间复杂度不是 O(n)？
看起来两轮遍历是 O(2n)，但实际最坏情况是：第一轮快慢指针在环内绕了接近一整圈才相遇，第二轮从头走到入口又走了一段。总访问节点数上限约为 3n，仍属 O(n)。真正要注意的是环非常小、链表极长时，k 很大，但常数因子不影响渐进复杂度。
如果面试中被问“能否只遍历一次”，答案是否定的——因为环入口位置无法仅凭一次扫描中的相对位移唯一确定，必须借助两次独立的线性扫描来解耦路径长度信息。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
