LeetCode 141 环形链表判断：哈希表与快慢指针解法
🌀 环形链表：当数据开始循环舞蹈
在计算机科学的世界里，链表是一种优雅而基础的数据结构。正常链表如同一条笔直的小路，从起点 (head) 出发，每个节点指向下一个节点，最终以空指针 (nullptr) 作为终点，标志着旅程的结束。
Head -> Node1 -> Node2 -> Node3 -> nullptr
然而，环形链表则打破了这种线性规则，它更像是一个神秘的莫比乌斯环，没有真正的终点。链表的某个节点不再指向空，而是指向链表中已经存在的另一个节点，形成了一个无尽的循环。
Head -> Node1 -> Node2 -> Node3 -> Node4 -> Node2...
🔍 解法一：哈希表法 - 记忆的艺术
解题思路
想象你是一位侦探，正在追踪一个可能陷入循环的线索。你需要记录下每一个经过的节点，就像在犯罪地图上钉上标记。每当遇到新节点时，你都要检查这个地点是否曾经出现过。
bool hasCycle(ListNode *head) {
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) | 需要存储所有访问过的节点 |
这种方法直观易懂，但需要额外的存储空间。哈希表的选择至关重要，它决定了查找效率。在 C++ 中，unordered_set 提供了平均 O(1) 的查找时间复杂度。
🏃♂️ 解法二：快慢指针法 - 龟兔赛跑的智慧
解题思路
受龟兔赛跑寓言的启发，我们让两个指针以不同速度遍历链表。如果存在环，快指针终将追上慢指针；如果不存在环，快指针会先到达终点。
指针移动示意：
Head -> Node1 -> Node2 -> Node3 -> Node4
slow: ^
fast: ^
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
- 指针移动顺序：先移动指针再判断，避免错过相遇点
- 循环终止条件：快指针或其 next 为 null 时即可确定无环
调试过程中，我最初忽略了 fast->next 的判空，导致在偶数长度链表上报错。通过添加这个检查，代码变得更加健壮。
🌈 思维与实现的分离
在解决算法问题时，思维过程和具体实现是两个不同的层面：
- 思维层面：考虑问题本质，寻找规律和模式
- 实现层面：将思维转化为代码，处理边界条件和语言特性
优秀的程序员能够在这两个层面间自如切换，既能看到森林，也能处理每棵树。
🎯 总结
环形链表判断是链表操作中的经典问题，两种解法各有千秋：
- 哈希表法：直观易懂，适合教学和理解问题本质
- 快慢指针法：空间高效，体现了算法优化的智慧
掌握这两种方法，不仅能解决 LeetCode 141 题，更能为处理更复杂的链表问题打下坚实基础。记住，在编程的世界里，有时候跑得快的兔子确实能教会我们很多！