LeetCode 141 题：环形链表检测算法

环形链表检测概述

在数据结构中，链表通常以空指针作为终点。但在环形链表中，某个节点会指向链表中已存在的节点，形成闭环。判断是否存在环是面试中的高频考点。

哈希表法

思路

最直观的方法是记录访问过的节点。遍历链表时，若发现当前节点已在集合中，说明存在环；若遍历结束未重复，则无环。

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

此方法逻辑简单，适合理解问题本质，但空间开销较大。

快慢指针法

思路

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

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; // 兔子每次两步
    }
     ; 
}