题目
需要判断一个单链表是否存在环，要求额外空间复杂度为O(1)。最合适的方法是（）。
题目类型：原创高频练习题
用途：用于帮助理解程序员相关考点和答案解析，不等同于官方真题。
正确答案
B
Floyd判环法只保存两个指针。若链表无环，快指针最终到达null；若有环，二者进入环后相对速度为每轮一步，最终一定相遇。
选项分析
A
错误。需要O(n)额外空间，而且复制有环链表本身也需先处理终止问题。
B
正确。时间O(n)、额外空间O(1)。
C
错误。环由结点引用关系决定，与相邻值是否相同无关。
D
错误。链表结点值排序不能反映next指针是否形成环。
本题为什么容易错
链表环是地址关系，不是数据重复。两个结点值相同很正常，真正需要观察的是沿next走是否回到已经经过的结点。
先看结论
简短答案
不使用额外集合，怎样判断单链表中是否存在环，正确答案是 B（使用快慢指针，慢指针每次一步、快指针每次两步，若相遇则存在环）。Floyd判环法只保存两个指针。若链表无环，快指针最终到达null；若有环，二者进入环后相对速度为每轮一步，最终一定相遇。
解析
易混淆概念对比表
| 概念 | 本题判断 | 区别要点 | 记忆提示 |
|---|---|---|---|
| 把所有结点复制到一个同样长的新链表 | 本题干扰项 | 错误。需要O(n)额外空间，而且复制有环链表本身也需先处理终止问题。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 使用快慢指针，慢指针每次一步、快指针每次两步，若相遇则存在环 | 本题正确答案 | 正确。时间O(n)、额外空间O(1)。 | 看到题干核心场景时优先联想到它 |
| 只比较相邻两个结点的值是否相等 | 本题干扰项 | 错误。环由结点引用关系决定，与相邻值是否相同无关。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 按结点值排序后判断 | 本题干扰项 | 错误。链表结点值排序不能反映next指针是否形成环。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
本题易混淆选项怎么区分
- 把所有结点复制到一个同样长的新链表：错误。需要O(n)额外空间，而且复制有环链表本身也需先处理终止问题。
- 只比较相邻两个结点的值是否相等：错误。环由结点引用关系决定，与相邻值是否相同无关。
- 按结点值排序后判断：错误。链表结点值排序不能反映next指针是否形成环。
复习
知识点详解
慢指针速度1、快指针速度2。进入环后快指针每轮相对慢指针前进1个结点，因此会追上。算法循环前应确保fast及fast.next非空。
备考速记
无环时快指针先出赛道，有环时快指针终会从后面追上慢指针。
Floyd算法 在空间复杂度场景中的作用
检测到相遇后，让一个指针回到链表头，另一个留在相遇点，二者都每次走一步，再次相遇的位置就是环入口。
拓展
同类题怎么考
- 在O(1)空间限制下判断链表环。
- 区分快慢指针相遇点与环入口。
Floyd算法 在程序员软考中的考法
题目同时出现链表判环和O(1)空间，基本锁定Floyd快慢指针；若问入口，再补第二阶段。
解题思路
题目把O(1)额外空间写得很明确，意味着不能用访问集合保存所有结点。两个指针即可完成判断，选B。
考点定位
判断是否有环与寻找环入口是两个步骤。相遇只能证明有环，若要找入口，还需让一个指针回到头结点，再让两者同速前进。
易错提醒
- 循环条件只检查fast不为空，访问fast.next时发生异常。
- 快慢指针第一次相遇后直接把相遇点当成环入口。
- 比较结点值而不是结点身份。
备考提示
- 先掌握判环，再单独推导找入口和计算环长。
- 用无环、头结点入环、中间入环三种链表手动画指针。
你可能还想了解
- 不用集合怎样判断链表有环？
- 快慢指针为什么一定会相遇？
- 相遇点就是环入口吗？
本文小结
Floyd算法用两个速度不同的指针在O(1)空间内判环；有环时二者最终相遇，无环时快指针到达null。