环形链表检测:哈希表与快慢指针实战
在数据结构的世界里,链表是最基础也最灵活的结构之一。普通链表像一条单行道,从起点出发,每个节点指向下一个,最终指向空指针结束旅程。但环形链表打破了这种线性规则,某个节点不再指向空,而是回指链表中已存在的节点,形成闭环。
解法一:哈希表法
思路很直观:遍历链表时记录访问过的节点。如果再次遇到同一个节点,说明存在环。
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) | 需存储所有访问过的节点 |
这种方法逻辑简单,适合快速理解问题本质,但需要额外的存储空间。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;
}
;
}


