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

环形链表基础

在数据结构中，普通链表是线性的，从头节点出发，每个节点指向下一个，最终指向空指针（nullptr）结束。而环形链表打破了这一规则，某个节点的 next 指针不再为空，而是指向链表中已存在的节点，形成闭环。

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

这种方法逻辑简单，但牺牲了空间换取时间效率。unordered_set 提供了平均 O(1) 的查找能力，适合对空间不敏感的场景。

解法二：快慢指针法

思路

受龟兔赛跑启发，设置两个指针，一个每次走一步（slow），一个每次走两步（fast）。如果链表有环，快指针终将追上慢指针；若无环，快指针会先到达终点。

代码实现

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