环形链表 II
Linked List Cycle II
如果链表有环，返回环的入口节点；没有环返回 null。
在力扣中练习题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
解题思路
Floyd · 相遇后对齐
先让快慢指针相遇，再从头和相遇点同速走
第 141 题只要求判断有没有环，本题还要找入口。快慢指针第一次相遇的位置不一定是入口，它只是追及点。
设 head 到入口距离为 a，入口到相遇点距离为 b，环长为 L。相遇时 slow 走了 a+b，fast 走了 2(a+b)，两者相差 L 的整数倍，化简得到 a = L-b。也就是说，从 head 到入口的距离，等于从相遇点继续走到入口的距离。
第 1 轮：slow → node-1，fast → node-2。
于是把 p 放回 head、q 留在相遇点，两者都每次走一步；它们第一次重合的位置就是入口。
p 回到 head，q 留在相遇点 node-3；接下来两者都每次走一步。
设 head 到入口为 a、入口到相遇点为 b、环长为 L。慢指针走了 a+b，快指针走了 2(a+b)，两者相差 L，因此 a = L-b，正好是从相遇点走到入口的距离。
自拟主例的入口在下标 2，而快慢指针在环内下标 3 相遇，两个位置不同。画面上先标出“相遇点”，再用第二阶段把“入口”找出来，避免把两者混为一谈。
易错点
- 把第一次相遇点直接当入口：只有 a = c 的特殊情况才恰好相等。
- 第二阶段让两个指针都从头出发：必须一个在 head、一个在相遇点。
- 判空只检查 fast：fast->next 为空时同样没有环。
哈希集合 · 第一个重复节点
沿链走，第一个第二次出现的节点就是入口
结果同样正确，但需要 O(n) 额外空间；主解法用 Floyd 把空间降到 O(1)。
如果用一个集合记录走过的节点，那么从 head 出发，第一个重复出现的节点正是环入口：入口之前的节点都只经过一次，进入环后才会再次遇到入口。
实现比 Floyd 直接得多，也不需要推导距离关系。代价是 O(n) 的集合空间，以及额外的哈希开销。
当链表很长而内存充足时，这个方案更容易写对；如果题目要求 O(1) 空间，就必须用 Floyd。
- 1建立空集合。
- 2沿 next 遍历，当前节点已在集合中就返回它。
- 3否则加入集合，继续；走到 null 返回 null。
易错点
- 把值存进集合：不同节点可能值相同，必须存节点地址。
- 返回上一个节点而不是当前重复节点：入口是第一次被再次访问的那个。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
head = [3,8,1,5,2]，2 的 next 指回 1slow、fast 从头出发；先确认有没有环，再谈入口。
查看 C++ 代码
延伸阅读
- Floyd 的第二阶段是“距离等式”的直接应用，理解 a = c 比背代码更重要。
- 判环、找入口、找重复数（287）本质上都可以用快慢指针在同一张图上完成。