数据结构：如何判断一个链表中是否存在环（Check for LOOP in Linked List）
目录
初始思考：什么叫“链表有环”？
❌ 第一种直接想法（失败）：我们是不是能“记住走过的节点”？
那我们换一个思路：我们能否只用两个指针来检测环？
第一步：定义两个指针
第二步：建立循环
初始思考：什么叫“链表有环”？
链表的本质是：
Node → Node → Node → NULL
但如果链表中某个节点的 next 指针不是 NULL，而是指向之前的某个节点：
Node → Node → Node ↑ ↓ ←←←←←←←←←←
这就变成了一个“环形结构”。
❓我们怎么知道某个链表有没有环？
你无法一次看完所有节点。你只能从头开始，一个一个往后走：
while (p != NULL) {p = p->next;
}
正常情况下你最终会走到 p == NULL
但是如果链表有环，你会一直绕圈，永远也走不到 NULL，程序变成死循环。
❌ 第一种直接想法（失败）：我们是不是能“记住走过的节点”？
想法：
每访问一个节点，就记住它；
如果某个节点我们第二次看到，就说明有环。
这个思路需要什么？
需要能“记住所有走过的节点”，并判断是否“已经访问过”
⚠️ 但我们没有 STL、没有哈希表、没有额外空间！
所以这个方法不符合第一性原则的最低资源要求，我们暂时排除。
那我们换一个思路：我们能否只用两个指针来检测环？
想象一下：
如果你在一个环形跑道上，有两个人：
一个人慢跑（每次走一步）
一个人快跑（每次走两步）
如果跑道没有环，快跑的人会直接跑出终点。
如果跑道是环形的，快跑的人迟早会“追上”慢跑的人！
这就是 Floyd’s Cycle Detection Algorithm（龟兔赛跑法）
我们现在从零构建它！
第一步：定义两个指针
slow = head;
fast = head;
-
slow每次走一步：slow = slow->next -
fast每次走两步：fast = fast->next->next
这一步是算法核心，“快指针”在追“慢指针”
第二步：建立循环
| 变量 | 含义 |
|---|---|
| slow | 模拟“正常访问”的一步步访问 |
| fast | 模拟“追赶检测”的两步步访问 |
| slow==fast | 表示 fast 追上 slow，说明有环 |
| fast==NULL | 表示链表已经结束，无环 |
问题：我们什么时候会出错？
-
如果
fast == NULL：说明走到尾部 -
如果
fast->next == NULL：再走一步就越界
我们必须确保两个指针不越界（避免访问 NULL 的 next）：
while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if (slow == fast) {// 二者相遇，说明有环}
}
❓为什么 slow 和 fast 相遇就说明有环？
因为只有在环中，快指针才有可能“绕回来追上慢指针”
就像操场上，跑得快的人终将追上慢跑的那个人。
如果没有环，fast 最终会变成 NULL 或 fast->next == NULL，循环终止。
如果链表中有环，两个指针最终会在环中某处相遇：
if (slow == fast)return 1; // 有环
空链表或一个节点链表怎么办？
-
如果
head == NULL：直接退出循环，返回 0 ✅ -
如果只有一个节点：
fast->next == NULL，也会直接退出 ✅
完整代码
int hasLoop(struct Node* head) {struct Node* slow = head;struct Node* fast = head;// Step 1: 同时从头开始，每次走一步和两步while (fast != NULL && fast->next != NULL) {slow = slow->next; // 慢指针走一步fast = fast->next->next; // 快指针走两步if (slow == fast) // 相遇 → 有环return 1;}// Step 2: 如果快指针走到了链表尾部，说明无环return 0;
}
时间 & 空间复杂度分析
| 复杂度 | 说明 |
|---|---|
| 时间复杂度 | O(n)，最坏情况 fast 会走到链表尽头（或追上 slow） |
| 空间复杂度 | O(1)，只用了两个指针变量，无需额外空间 |
我们从“什么都不会”出发，只知道我们：
-
只能走
->next -
不允许记录历史
-
想办法“检测重复访问”
最终我们想到“相遇 → 有环”的思路，从而构建出用两个指针的检测算法。