环形链表概述
在计算机科学中，链表是一种基础数据结构。普通链表从起点 (head) 出发，每个节点指向下一个节点，最终以空指针 (nullptr) 作为终点。
环形链表则打破了线性规则，链表的某个节点不再指向空，而是指向链表中已经存在的另一个节点，形成了一个无尽的循环。
解法一：哈希表法
解题思路
记录每一个经过的节点，每当遇到新节点时，检查该节点是否曾经出现过。
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) 的查找时间复杂度。
解法二：快慢指针法
解题思路
受龟兔赛跑寓言启发，让两个指针以不同速度遍历链表。如果存在环，快指针终将追上慢指针；如果不存在环，快指针会先到达终点。
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 的判空，导致在偶数长度链表上报错。通过添加这个检查，代码变得更加健壮。
思维与实现的分离
在解决算法问题时，思维过程和具体实现是两个不同的层面：
- 思维层面：考虑问题本质，寻找规律和模式
- 实现层面：将思维转化为代码，处理边界条件和语言特性
优秀的程序员能够在这两个层面间自如切换，既能看到森林，也能处理每棵树。
总结
环形链表判断是链表操作中的经典问题，两种解法各有千秋：
- 哈希表法：直观易懂，适合教学和理解问题本质
- 快慢指针法：空间高效，体现了算法优化的智慧
掌握这两种方法，不仅能解决环形链表检测问题，更能为处理更复杂的链表问题打下坚实基础。