🌀 环形链表：当数据开始循环舞蹈
在数据结构的世界里，链表是最基础的结构之一。正常链表像一条单行道，从头节点（head）出发，每个节点指向下一个，最终遇到空指针（nullptr）结束旅程。
但环形链表打破了这种线性规则。某个节点的 next 指针不再指向 null，而是回指到链表中已存在的某个节点，形成了一个闭环。检测这种结构是否存在环，是面试中的经典考题。
🔍 解法一：哈希表法 - 空间换时间
核心思路
最直观的方法是记录所有访问过的节点。我们可以使用一个集合来存储遍历过程中遇到的节点地址。如果再次遇到集合中已有的节点，说明存在环；如果遍历到空指针，则无环。
bool hasCycle(ListNode *head) {
std::unordered_set<ListNode*> visited;
while (head != nullptr) {
if (visited.count(head)) {
return true; // 发现重复访问，存在环
}
visited.insert(head);
head = head->next;
}
return false; // 正常到达终点，无环
}
性能分析
- 时间复杂度：O(n)。最坏情况下需要遍历整个链表。
- 空间复杂度：O(n)。需要额外存储所有访问过的节点。
这种方法逻辑简单，容易理解，但在内存敏感的场景下不是最优解。
🏃♂️ 解法二：快慢指针法 - 龟兔赛跑的智慧
核心思路
受寓言故事启发，我们让两个指针以不同速度移动。慢指针每次走一步，快指针每次走两步。如果链表有环，快指针终将追上慢指针；如果没有环，快指针会先到达终点。
bool hasCycle(ListNode *head) {
if (head == nullptr || head->next == nullptr) {
return false;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (fast == nullptr || fast->next == nullptr) {
return false; // 快指针到达终点，无环
}
slow = slow->next; // 乌龟每次一步
fast = fast->next->next; // 兔子每次两步
}
return true; // 相遇，存在环
}
性能优势
- 时间复杂度：O(n)。线性时间解决问题。
- 空间复杂度：O(1)。仅需两个指针变量，常数空间。
这是空间最优解，也是业界推荐的标准写法。它体现了双指针技巧在链表问题中的威力。
💻 代码实现与调试心得
在实际编码时，有几个坑需要注意：
- 边界条件：空链表或单节点链表直接返回 false，避免空指针异常。
- 判空顺序：检查
fast->next前必须先确认fast不为空，防止段错误。 - 偶数长度陷阱：如果只判断
fast != nullptr，在偶数长度且无环的链表中可能漏掉终止条件，必须同时检查fast->next。
调试初期我常忽略 fast->next 的判空，导致在特定测试用例上崩溃。加上这个检查后，代码健壮性显著提升。
🎯 总结
环形链表检测是链表操作中的必考题，两种方法各有侧重：
- 哈希表法：直观易懂，适合快速验证逻辑，但占用额外内存。
- 快慢指针法：空间效率极高，是工程实践中的首选方案。
掌握这两种思路，不仅能解决 LeetCode 141 题，更能为处理更复杂的链表问题打下坚实基础。记住，有时候跑得快的兔子确实能教会我们很多！