你好！我是你的 OI 教练。今天我们要讨论的是链表题目中极具代表性的基础算法：环形链表判定（Linked List Cycle）。

这道题在 LeetCode 中虽然简单，但在 NOI 竞赛中，它是理解双指针思想以及图论找环逻辑的重要基石。

一、 预备知识点 checklist

1. 链表结构：理解单向链表的指针逻辑，知道 next 指向下一个内存地址。
2. 哈希表/集合：用于记录访问过的节点地址（暴力解法）。
3. 弗洛伊德找环算法（Floyd's Cycle-Finding Algorithm）：俗称“快慢指针”，这是解决此题的最优 $O(1)$ 空间算法。
4. 图论基础：链表可以看作是每个点出度为 1 的特殊有向图。

二、 题目描述：环形链表 (Linked List Cycle)

题目背景： 在内存管理中，如果指针指向了之前的节点，就会形成环，导致遍历程序进入死循环。你的任务是编写一个鲁棒的判定程序。

题目描述： 给定一个单链表的头节点 $head$，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 $next$ 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 $pos$ 来表示链表尾部连接到链表中的位置（索引从 0 开始）。如果 $pos$ 是 -1，则在该链表中没有环。

注意：$pos$ 仅用于题目数据说明，输入数据中并不会直接给你这个 $pos$，你只能通过链表节点的指针进行判断。

输入格式 (Standard Input)：

• 第一行包含两个整数 $n$ 和 $pos$，分别表示链表中的节点数和环连接的位置。
• 第二行包含 $n$ 个整数，表示链表中各节点的值。

输出格式 (Standard Output)：

• 如果链表中存在环，输出 true，否则输出 false。

输入样例 1：

4 1
3 2 0 -4

(说明：尾部节点 -4 连接到索引为 1 的节点 2，形成环)

输出样例 1：

true

数据规模与约定：

• $0 \le n \le 10^4$
• $-10^5 \le \text{节点值} \le 10^5$
• $pos$ 为 $-1$ 或链表中的有效索引。
• 时间限制：1.0s
• 内存限制：128MB
• 进阶要求：你能用 $O(1)$（即常量）内存解决此问题吗？

三、 教练的草稿纸：启发式推理过程

请在草稿纸上跟我画两个场景：

1. 模拟“跑道找环”

• 想象一个操场跑道。有两个运动员：慢鸟（Slow）和快鹰（Fast）。
• 规则：慢鸟每秒走 1 步，快鹰每秒走 2 步。
• 情景 A：直线跑道（无环）
  • 快鹰会迅速到达终点（指向 nullptr），两人永远不会相遇。
• 情景 B：环形跑道（有环）
  • 两人都会进入环中。
  • 因为快鹰比慢鸟快，他们的距离每一秒都会缩短 1 步。
  • 结论：在环里，快鹰一定会在某一时刻“套圈”慢鸟，即两人再次指向同一个节点。

2. 时间与空间复杂度思考过程

• 方案一：哈希表记账
  • 每走一步，把节点的地址（指针本身）存入 std::set。
  • 如果发现当前地址已经出现过，说明有环。
  • 代价：时间 $O(n \log n)$ 或 $O(n)$，但空间需要 $O(n)$ 来存地址。
• 方案二：快慢指针（NOI 推荐）
  • 定义两个指针 slow = head, fast = head。
  • 循环中：slow = slow->next, fast = fast->next->next。
  • 注意判断条件：必须检查 fast 和 fast->next 是否为空，防止程序由于访问非法内存崩溃（Runtime Error）。

四、 算法流程图 (Mermaid 风格)

为了保证渲染成功，我们避开特殊字符：

graph TD
    A("开始判定") --> B("初始化 Slow 和 Fast 指向 Head")
    B --> C{"Fast 且 Fast 的 Next 不为空?"}
    
    C -- "否" --> D("无路可走 返回 False")
    C -- "是" --> E("Slow 移动 1 步")
    E --> F("Fast 移动 2 步")
    
    F --> G{"Slow 等于 Fast 吗?"}
    G -- "是" --> H("快慢相遇 返回 True")
    G -- "否" --> C
    
    D --> I("结束")
    H --> I

五、 读题关键词与坑点总结

1. 关键词“索引 pos”：
   • 坑点：新手常想着用 pos。请记住，题目明确说 $pos$ 只是说明数据结构用的。在代码逻辑里，你完全看不到 $pos$，只能靠指针移动。
2. 关键词“常量内存”：
   • 这意味着你不能开数组，不能开 std::set。这是强制你写双指针。
3. 内存访问安全（Segmentation Fault）：
   • 在执行 fast->next->next 之前，必须先判断 fast 是否为空，再判断 fast->next 是否为空。这是 NOI 中非常基础但极易丢分的点。
4. 节点值还是节点地址？：
   • 环的判定是基于“同一个节点”（内存地址相同），而不是“同样数值的节点”。链表中可能存在多个节点值都等于 1 的不同节点。

六、 复杂度分析与建议

• 时间复杂度：
  • 无环：$O(n)$。
  • 有环：慢指针进入环后，快指针在 $O(\text{环长度})$ 时间内一定追上慢指针。总时间仍为 $O(n)$。
• 空间复杂度：
  • 快慢指针法仅使用两个额外指针，为 $O(1)$。
• 优化建议：
  • 在竞赛中，如果 $n$ 特别大（如 $10^7$），注意不要在循环里写复杂的逻辑，保证快慢指针的纯净度。
  • 判定 nullptr 时，使用 while(fast && fast->next) 是最简洁的写法。

教练寄语： 链表找环是“双指针”技巧最纯粹的体现。如果能理解快鹰如何“套圈”慢鸟，你就掌握了此类问题的核心！加油。