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

问题背景

在数据结构中，链表是一种基础且重要的线性结构。普通链表从头节点（head）出发，每个节点指向下一个节点，最终以空指针（nullptr）结束。而环形链表则打破了这一规则，某个节点的 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)，需要存储所有访问过的节点。

解法二：快慢指针法

思路解析

受龟兔赛跑寓言启发，我们设置两个指针，一个每次走一步（慢指针），一个每次走两步（快指针）。

• 若链表无环，快指针会先到达终点（nullptr）。
• 若链表有环，快指针最终会在环内追上慢指针。

这是空间最优的解法，无需额外存储。

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 ; 
        }
        slow = slow->next;      
        fast = fast->next->next;
    }
     ; 
}