环形链表检测：哈希表与快慢指针实战

环形链表检测：哈希表与快慢指针实战

在数据结构的世界里，链表是最基础也最灵活的结构之一。普通链表像一条单行道，从起点出发，每个节点指向下一个，最终指向空指针结束旅程。但环形链表打破了这种线性规则，某个节点不再指向空，而是回指链表中已存在的节点，形成闭环。

解法一：哈希表法

思路很直观：遍历链表时记录访问过的节点。如果再次遇到同一个节点，说明存在环。

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; 
    }
     ; 
}