LeetCode 141：环形链表检测的经典解法

环形链表检测：从基础到优化

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

方法一：哈希表法

最直观的思路是记录所有经过的节点。就像侦探在地图上钉下标记，每遇到一个新节点就检查是否已经出现过。

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; // 相遇，存在环
}