LeetCode 141：环形链表判断的两种解法

🌀 环形链表：当数据开始循环舞蹈

在数据结构的世界里，链表是最基础的结构之一。正常链表像一条单行道，从头节点（head）出发，每个节点指向下一个，最终遇到空指针（nullptr）结束旅程。

但环形链表打破了这种线性规则。某个节点的 next 指针不再指向 null，而是回指到链表中已存在的某个节点，形成了一个闭环。检测这种结构是否存在环，是面试中的经典考题。

🔍 解法一：哈希表法 - 空间换时间

核心思路

最直观的方法是记录所有访问过的节点。我们可以使用一个集合来存储遍历过程中遇到的节点地址。如果再次遇到集合中已有的节点，说明存在环；如果遍历到空指针，则无环。

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)。需要额外存储所有访问过的节点。

这种方法逻辑简单，容易理解，但在内存敏感的场景下不是最优解。

🏃‍♂️ 解法二：快慢指针法 - 龟兔赛跑的智慧

核心思路

受寓言故事启发，我们让两个指针以不同速度移动。慢指针每次走一步，快指针每次走两步。如果链表有环，快指针终将追上慢指针；如果没有环，快指针会先到达终点。

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