你好！我是你的 OI 教练。在上一节课中，我们掌握了如何判定链表是否有环。今天我们要挑战它的升级版：环形链表 II（Linked List Cycle II）。

这道题不仅要求你判断“有没有环”，还要求你精准定位“环的入口在哪里”。这涉及到一个非常经典的数论/几何推导，是双指针算法的高阶应用。

一、 预备知识点 checklist

1. 快慢指针（Floyd 判环）：理解快慢指针相遇的必然性。
2. 代数推导：能够通过位移公式推导出指针相遇后的运动规律。
3. 哈希表（暴力参考）：理解空间换时间的权衡。
4. 静态链表思想：在竞赛中如何用数组维护指针关系。

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

题目背景： 在检测到内存循环引用（环）后，系统需要找到循环的起始点以便断开连接。

题目描述： 给定一个单链表的头节点 $head$，返回链表开始入环的第一个节点。如果链表无环，则返回 null。 为了表示环，我们使用整数 $pos$ 表示链表尾部连接到链表中的索引（从 0 开始）。如果 $pos$ 为 -1，则没有环。

注意：你不能修改链表，且不允许直接使用输入中的 $pos$。

输入格式 (Standard Input)：

• 第一行包含两个整数 $n$ 和 $pos$，分别表示节点数和环的入口索引。
• 第二行包含 $n$ 个整数，表示链表中各节点的值。

输出格式 (Standard Output)：

• 如果无环，输出 no cycle。
• 如果有环，输出入环节点的索引值（即 $pos$）以及该节点的值。格式为：tail connects to node index pos with value val。

输入样例 1：

4 1
3 2 0 -4

输出样例 1：

tail connects to node index 1 with value 2

数据规模与约定：

• $0 \le n \le 10^4$
• $-10^5 \le \text{节点值} \le 10^5$
• $pos \in [-1, n-1]$
• 时间限制：1.0s
• 内存限制：128MB
• 进阶要求：使用 $O(1)$ 空间复杂度。

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

这道题的核心不在于代码，而在于草稿纸上的推导。

1. 变量定义

画一个形状像“6”的链表：

• 设 a 为从“头节点”到“环入口”的距离。
• 设 b 为从“环入口”到“快慢指针相遇点”的距离。
• 设 c 为从“相遇点”继续走回到“环入口”的距离。
• 环的长度为 L = b + c。

2. 数学推导

当快慢指针相遇时：

• 慢指针走的距离：$S = a + b$
• 快指针走的距离：$F = a + nL + b$ （$n$ 是快指针在环里多转的圈数，$n \ge 1$）
• 因为快指针速度是慢指针的 2 倍，所以：$F = 2S$
• 代入公式：$a + nL + b = 2(a + b)$
• 整理得：$a = nL - b = (n-1)L + (L-b)$
• 因为 $L-b = c$，所以：$a = (n-1)L + c$

3. 结论

这个公式意味着：从头节点出发到环入口的距离 (a)，等于从相遇点出发绕环 n-1 圈后再回到环入口的距离 (c)。

操作策略：相遇后，把其中一个指针放回 head，另一个留在相遇点，两个指针同时每秒走一步。它们再次相遇的地方，就是环的入口！

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

graph TD
    A("开始") --> B("初始化 Slow 和 Fast 指向 Head")
    B --> C{"Fast 且 Fast的Next 不为空?"}
    
    C -- "否" --> D("无环 返回 null")
    C -- "是" --> E("Slow 走 1 步, Fast 走 2 步")
    
    E --> F{"Slow 等于 Fast 吗?"}
    F -- "否" --> C
    F -- "是" --> G("相遇点已找到")
    
    G --> H("将指针 PTR1 设为 Head")
    H --> I("将指针 PTR2 设为 Slow 相遇点")
    
    I --> J{"PTR1 等于 PTR2 吗?"}
    J -- "否" --> K("PTR1 和 PTR2 各走 1 步")
    K --> J
    
    J -- "是" --> L("PTR1 即为环入口节点")
    L --> M("返回结果")
    D --> M
    M --> N("结束")

五、 复杂度分析思考过程

• 时间复杂度：

  1. 寻找相遇点：最坏情况下快指针走 $2n$ 步，$O(n)$。
  2. 寻找入口：两个指针走的距离之和也是 $O(n)$。
  • 结论：总时间复杂度为 $O(n)$。

• 空间复杂度：

  • 哈希表法：存地址需要 $O(n)$。
  • 双指针法：只用了常数个指针变量。
  • 结论：空间复杂度 $O(1)$。

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

1. “返回节点”与“索引 pos”：
   • 在竞赛中，通常让你输出节点的值或其在原始输入中的位置。注意题目要求的输出格式，不要习惯性只返回 true/false。
2. “不允许修改链表”：
   • 有些“邪道”做法是每遍历一个节点就把它指向一个特定的特殊节点（如 nullptr），以此判断环。这种做法被本题禁用。
3. 无环判断：
   • 坑点：如果链表只有一个节点且无环，快指针的 fast->next 立即为空。
   • 对策：始终先写 if (!head || !head->next) return nullptr;。
4. 快慢指针的起始位置：
   • 一定要同时从 head 出发。如果慢指针在 head，快指针在 head->next，后面的数学推导公式会发生偏移。

教练建议

这道题是 OI 面试或初赛中非常高频的数学建模题。建议在练习时，不要直接敲代码，先在草稿纸上把 $a = (n-1)L + c$ 推导一遍。理解了数学原理，代码只是顺理成章的翻译！