环形链表
Linked List Cycle
判断一条链表里是否存在环（某个节点的 next 指回了之前的节点）。
在力扣中练习题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
提示：
- 链表中节点的数目范围是
[0, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
解题思路
快慢指针 · Floyd 判环
在环里，跑得快的那个一定追得上慢的
最直接的办法是沿途记录访问过的节点，一旦重复就说明有环；但这需要 O(n) 的哈希集合。
Floyd 判环只用两个指针：slow 每次走一步，fast 每次走两步。如果链表有终点，fast 会先到 null；如果有环，fast 会先进入环，然后在环里一圈圈追 slow。
为什么一定追得上？进入环后，fast 每轮比 slow 多走一步，两者距离每轮减少 1，最多经过环长那么多轮就会重合。slow 不需要跑满一圈。
第 1 轮：slow → node-1，fast → node-2，还没有相遇。
自拟主例的环入口在下标 3，fast 和 slow 进入环的时间不同；画面上两个指针最终在同一节点重合，而不是在入口处相遇。题目只要求判断有没有环，所以第一次重合就可以返回。
易错点
- 只判断 fast 为空：fast->next 也可能为空，取 fast->next->next 会崩溃。
- 先移动再判断时漏掉初始重合：本题初始都在 head，不能一上来就返回 true。
- 把“值相等”当成相遇：必须比较节点地址。
哈希集合 · 记录访问
走过的节点记下来，第二次遇到就是环
逻辑最直白，但需要 O(n) 额外空间；主解法用两个指针把空间降到 O(1)。
从 head 开始遍历，把每个节点地址放进 unordered_set。如果当前节点已经在集合里，说明之前来过，存在环；如果走到 null，说明没有环。
它不依赖快慢指针的追及证明，非常适合快速验证。代价是额外 O(n) 的集合空间，而且需要能对节点地址做哈希。
如果题目还要求返回环入口，这个方案第一次重复访问的节点就是入口。
- 1建立空的节点集合。
- 2沿 next 遍历，检查当前节点是否出现过。
- 3重复出现返回 true；走到 null 返回 false。
易错点
- 存节点的值而不是地址：不同节点可能值相同，会误判。
- 遍历条件写成 p->next：会漏掉尾节点本身。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
head = [7,4,9,2,6,1]，1 的 next 指回 2slow、fast 都从头出发；fast 每轮走两步，slow 走一步。
查看 C++ 代码
延伸阅读
- Floyd 判环是链表题里少数不借助额外空间的“追及”技巧，后面找环入口会继续用到。
- 快指针走两步、慢指针走一步只是最常见配速；关键是两者在环内的相对速度非零。