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

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

在数据结构的世界里，链表是最基础的结构之一。普通链表像一条单行道，从头节点出发，每个节点指向下一个，最终指向空指针结束旅程。而环形链表则打破了线性规则，某个节点的 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)	需存储所有访问过的节点

方法二：快慢指针法

这是更优的方案，灵感来自'龟兔赛跑'。让两个指针同时从头出发，一个每次走一步（慢），一个每次走两步（快）。如果存在环，快指针终将追上慢指针；如果不存在环，快指针会先到达终点。

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; // 兔子每次两步
    }
    return true; // 相遇，存在环
}

这里有个细节需要注意：初始化时 fast 设为 head->next 可以避免进入循环前就判相等，当然也可以都从 head 开始并在循环内先移动再判断。关键是边界条件处理要严谨。

指标	值	说明
时间复杂度	O(n)	线性时间解决问题
空间复杂度	O(1)	仅需两个指针，常数空间

调试心得

在实际编码中，有几个坑值得注意：

1. 边界检查：空链表或单节点链表直接返回 false。
2. 判空顺序：检查 fast->next 之前必须先确认 fast 不为空，防止空指针异常。
3. 逻辑清晰：思维层面确定规律后，实现时要仔细处理语言特性带来的边界差异。

掌握这两种方法，不仅能解决此类题目，更能培养对链表结构的敏感度。