13、检测链表中的环：快慢指针法、哈希表法、环的入口检测
链表中的环，说白了就是一个节点通过 next 指针又指回了前面某个节点，形成一个闭环。这个问题在面试中出现的频率极高，我当年面试时就被问过不止一次。更关键的是，在实际项目中，如果你不小心让链表产生了环，遍历操作就会陷入死循环——嗯，我确实遇到过这种尴尬的情况。
13.1 什么是链表中的环？
先看一个简单的环结构：
1 → 2 → 3 → 4 → 5 → 6
↑ |
|______________|节点 6 的 next 指向了节点 3，这就形成了一个环。从节点 1 开始遍历，永远走不到 NULL。
环带来的问题很明显：
- 遍历会无限循环
- 内存释放时可能遗漏节点
- 某些算法（如归并排序）会出错
所以，检测环的存在是链表操作中的基本功。
13.2 快慢指针法（Floyd 判环算法）
这个方法我个人非常喜欢。思路很简单：两个指针，一个每次走一步，另一个每次走两步。如果有环，它们一定会相遇。
为什么？你想想看，如果跑道是环形的，跑得快的人最终会追上跑得慢的人。这就是 Floyd 判环算法的核心思想。
// 检测链表是否有环 - 快慢指针法
int hasCycle(struct ListNode *head) {
if (head == NULL || head->next == NULL) {
return 0; // 空链表或只有一个节点，不可能有环
}
struct ListNode *slow = head;
struct ListNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next; // 慢指针走一步
fast = fast->next->next; // 快指针走两步
if (slow == fast) {
return 1; // 相遇了，有环
}
}
return 0; // 快指针走到头了，无环
}时间复杂度：O(n)，空间复杂度：O(1)。这是最推荐的方法。
我的经验：快慢指针法不仅用于判环，还可以用来找链表的中间节点。我在做嵌入式系统中的任务调度器时，就用它来检测任务链表是否出现了循环依赖。
13.3 哈希表法
这个方法更直观：遍历链表，把每个节点的地址存到哈希表里。如果某个节点地址已经存在，说明有环。
// 检测链表是否有环 - 哈希表法
#include <stdbool.h>
#include <uthash.h> // 假设使用 uthash 库
struct hashTable {
struct ListNode *node;
UT_hash_handle hh;
};
int hasCycleHash(struct ListNode *head) {
struct hashTable *set = NULL;
struct hashTable *tmp = NULL;
struct ListNode *cur = head;
while (cur != NULL) {
// 检查当前节点是否已在哈希表中
HASH_FIND_PTR(set, &cur, tmp);
if (tmp != NULL) {
return 1; // 找到了，有环
}
// 插入当前节点
tmp = (struct hashTable *)malloc(sizeof(struct hashTable));
tmp->node = cur;
HASH_ADD_PTR(set, node, tmp);
cur = cur->next;
}
return 0; // 遍历完，无环
}注意：哈希表法虽然直观，但空间复杂度是 O(n)。在嵌入式系统中，内存往往有限，我个人更倾向于快慢指针法。我曾经在一个内存只有 64KB 的 MCU 上调试代码，哈希表法直接导致堆溢出——从那以后，我养成了先评估内存再选算法的习惯。
13.4 环的入口检测
找到环还不够，有时候我们需要知道环的入口在哪里。比如在修复链表时，必须找到环的起始点才能断开它。
Floyd 算法不仅能判环，还能找入口。方法分两步：
- 用快慢指针找到相遇点
- 从相遇点和头节点同时出发，每次走一步，再次相遇的位置就是环的入口
为什么会这样？这里有个数学推导：
- 设头节点到环入口的距离为 a
- 环入口到相遇点的距离为 b
- 相遇点继续走到环入口的距离为 c
- 慢指针走了 a + b，快指针走了 a + b + k*(b+c)
- 因为快指针速度是慢指针的 2 倍，所以 2*(a+b) = a + b + k*(b+c)
- 化简得 a = (k-1)*(b+c) + c
- 也就是说，从头节点到入口的距离，等于从相遇点绕环 k-1 圈再到入口的距离
嗯，数学上可能有点绕。但代码实现其实很简单：
// 找到环的入口节点
struct ListNode *detectCycle(struct ListNode *head) {
if (head == NULL || head->next == NULL) {
return NULL;
}
struct ListNode *slow = head;
struct ListNode *fast = head;
int hasCycle = 0;
// 第一步：找相遇点
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
hasCycle = 1;
break;
}
}
if (!hasCycle) {
return NULL; // 无环
}
// 第二步：找环入口
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // 返回环入口节点
}关键点：第二步中，两个指针都只走一步。它们再次相遇的位置，就是环的入口。
13.5 三种方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 能否找入口 | 适用场景 |
|---|---|---|---|---|
| 快慢指针法 | O(n) | O(1) | 能 | 通用，内存受限时首选 |
| 哈希表法 | O(n) | O(n) | 能（记录入口） | 内存充足，代码可读性优先 |
| 标记法（修改节点） | O(n) | O(1) | 能 | 允许修改链表结构时 |
避坑指南：我曾经在调试一个通信协议栈时，用快慢指针法检测到了环，但没找到入口就直接把相遇点断开了——结果链表结构被破坏，数据全乱了。记住：只判环不改链表，除非你明确知道入口在哪。
13.6 知识体系总览
下面这张图总结了链表环检测的核心知识点：
13.7 实际项目中的选择建议
说了这么多，到底该用哪种方法？我根据实际经验给点建议：
- 嵌入式环境（内存小）：无脑选快慢指针法。空间 O(1) 是硬道理。
- PC 端开发（内存充足）：哈希表法更易读，调试时也方便打印节点信息。
- 需要修复环：必须用快慢指针法找入口，然后断开。
- 不允许修改链表：别用标记法，用前两种。
重要提醒：快慢指针法中，快指针每次走两步，慢指针每次走一步。如果你改成快指针走三步，虽然也能相遇，但可能错过某些情况下的相遇点，而且代码更难理解。我见过有人为了「优化」改成三步，结果在特定环结构下永远不相遇——嗯，调试了一整天。
链表环检测，说白了就是「有没有环」和「环在哪」两个问题。快慢指针法一个算法全搞定，这也是它成为经典的原因。你想想看，一个 O(1) 空间的算法，能同时解决两个问题，还有什么理由不用它呢？