LeetCode 141 环形链表检测：哈希表与快慢指针法

LeetCode 141 环形链表检测：哈希表与快慢指针法

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

在计算机科学的世界里，链表是一种优雅而基础的数据结构。正常链表如同一条笔直的小路，从起点 (head) 出发，每个节点指向下一个节点，最终以空指针 (nullptr) 作为终点，标志着旅程的结束。

Head
Node1
Node2
Node3
nullptr

然而，环形链表则打破了这种线性规则，它更像是一个神秘的莫比乌斯环，没有真正的终点。链表的某个节点不再指向空，而是指向链表中已经存在的另一个节点，形成了一个无尽的循环。

Head
Node1
Node2
Node3
Node4

🔍 解法一：哈希表法 - 记忆的艺术

解题思路

想象你是一位侦探，正在追踪一个可能陷入循环的线索。你需要记录下每一个经过的节点，就像在犯罪地图上钉上标记。每当遇到新节点时，你都要检查这个地点是否曾经出现过。

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) 的查找时间复杂度。

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

解题思路

受龟兔赛跑寓言的启发，我们让两个指针以不同速度遍历链表。如果存在环，快指针终将追上慢指针；如果不存在环，快指针会先到达终点。

指针移动

Head
Node1
Node2
Node3
Node4
slow
fast

bool hasCycle(ListNode *head){
    (head ==  || head->next == ){
         ;
    }
    ListNode* slow = head;
    ListNode* fast = head->next;
    (slow != fast){
        (fast ==  || fast->next == ){
             ; 
        }
        slow = slow->next; 
        fast = fast->next->next; 
    }
     ; 
}