LeetCode 141: 环形链表判断算法详解

问题背景

在计算机科学中，链表是一种基础数据结构。正常链表从起点 (head) 出发，每个节点指向下一个节点，最终以空指针 (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) 的查找效率。

解法二：快慢指针法

解题思路

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

slow: Head -> Node1 -> Node2 -> Node3
fast: Head -> Node2 -> Node4 -> ...

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