[141] 环形链表 (Linked List Cycle)

标签：链表 双指针 快慢指针
难度：🟢 Easy

🧠 核心思维：快慢指针 (Floyd 判圈算法)

TIP

物理直觉： 在环形跑道上，跑得快的人（兔子）一定会从后面追上跑得慢的人（乌龟）。

• 快指针 (fast)：每次走 2 步。
• 慢指针 (slow)：每次走 1 步。

结局推演

1. 无环：Fast 指针会遇到 nullptr (直接冲过终点)。
2. 有环：Fast 指针一定会再次追上 Slow 指针，即 fast == slow。

---

💻 标准代码 (C++)

bool hasCycle(ListNode *head) {
    // 特判：如果跑道都没修好，肯定没环
    if (head == nullptr || head->next == nullptr) return false;
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    // > [!WARNING] 崩溃高发区
    // 兔子跑得快，必须保证：
    // 1. 兔子当前脚下有路 (fast != nullptr)
    // 2. 兔子跳的下一步也有路 (fast->next != nullptr)
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;          // 🐢 慢走1步
        fast = fast->next->next;    // 🐇 快走2步
        
        if (slow == fast) {
            return true; // 💥 相遇即有环
        }
    }
    
    return false; // 🏃 跑到尽头即无环
}

📊 复杂度分析

NOTE

• 时间复杂度：。如果有环，快慢指针在环内走的圈数是常数级的，不会无限死循环。

• 空间复杂度：。我们只使用了 slow 和 fast 两个指针，没有使用哈希表。

快慢指针的空指针防御

问：在写 fast = fast->next->next 时，为什么不需要检查 fast->next->next != nullptr？

答：

• 崩溃的根源：程序崩溃（Segmentation Fault）通常是因为解引用空指针（即访问 nullptr->next）。
• 逻辑防线：循环条件 while (fast != nullptr && fast->next != nullptr) 已经确保了 fast 和 fast->next 都是有效节点。
• 赋值安全：
  • fast->next->next 实际上是访问 (fast->next)->next。因为 fast->next 已确认非空，所以访问它的成员是安全的。
  • 如果 fast->next 是最后一个节点，其 next 值为 nullptr。将 nullptr 赋值给 fast 是合法的（只是不能访问 fast->val）。下一轮循环会因为 fast == nullptr 而正常退出。

std::set 与 std::unordered_set 的复杂度差异

问：在链表查重或找环时，如果把 unordered_set 换成 set，复杂度有何变化？

答：时间复杂度从 退化为 。

特性	std::unordered_set	std::set
底层实现	哈希表 (Hash Table)	红黑树 (Red-Black Tree)
单次操作	平均	(树的高度)
N次操作总耗时
特点	无序，速度极快	有序 (自动排序)，速度稍慢
适用场景	快速查重、查找	需要数据有序输出、范围查找

结论：在算法题中（如两数之和、环形链表），除非题目明确要求输出有序结果，否则永远优先使用 unordered_set。