快慢指针（也叫 Floyd 龟兔赛跑）用一快一慢两个指针，在链表上跑一遍就能判断有没有环。如果有环，两个指针一定会在环里某个节点相遇。
为什么一快一慢必定相遇
把环想象成一个跑道：
- slow 每步走 1 格
- fast 每步走 2 格
如果链表无环，fast 会先走到 nullptr —— 没相遇就退出。
如果链表有环，fast 会先进入环。一旦两个指针都在环里，每走一步它们的距离就缩小 1（因为相对速度是 1 格/步）。距离最多是环长 - 1，所以最多走环长次就追上 —— 必然相遇。
代码
bool hasCycle(Node* head) {
Node *slow = head, *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}注意循环条件 fast != nullptr && fast->next != nullptr —— 因为 fast->next->next 要两步都存在才能走。
复杂度
- 时间：O(n) — 没有环时 fast 最多走 n/2 步；有环时最多走 n 步（追上）
- 空间：O(1) — 只用两个指针，不需要额外存储
如果用哈希表记录访问过的节点也能判环，但空间是 O(n)，败给快慢指针。
应用
快慢指针的套路还能解决：
- 找链表中点（fast 走完时 slow 正好在中间）
- 找倒数第 k 个节点（fast 先走 k 步，再一起走）
- 找环的入口（相遇后 slow 回头、fast 留下，再各走 1 步，再次相遇就是入口）
在动画里看什么
- slow 指针（浅蓝标签）一格一格走
- fast 指针（深蓝标签）两格两格走
- 末尾若有暖红色弧线，说明链表末尾连回某个前面的节点，形成了环
- 两个指针同时停在一个节点时，节点变成暖红色 —— 追上了