环形链表 II

这道题比判断有环多问了什么

LeetCode 141 只问链表里有没有环，快慢指针一相遇就能返回 true。本题要的更多：把环的入口节点找出来，也就是链表从哪个节点开始绕圈；若无环则返回 null。直观的做法是哈希集合——边走边把访问过的节点存进集合，第一个重复见到的节点就是入口，时间 O(n) 但空间也是 O(n)。进阶目标是不开任何额外结构，只靠几个指针把入口逼出来。

快慢指针为什么一定相遇，不会互相跳过

slow 每次走一步、fast 每次走两步。只要有环，两个指针迟早都会进环，此后每一轮 fast 与 slow 的距离恰好缩短一步——一步一步逼近，不存在「跨过去错过了」的可能，所以必然在环内某个位置相遇。若无环，fast 会先撞到 null，循环自然结束、返回 null。

要强调的是，这次相遇只证明环存在，相遇点一般并不是环入口——fast 是在环里绕圈追上 slow 的，追上的位置取决于环的形状。把相遇点直接当答案返回，是这道题最常见的错误。

为什么从头和相遇点同速走，会在入口碰头

设链表头到环入口的距离为 a，入口沿环走到相遇点的距离为 b，环长为 c。相遇那一刻 fast 的路程是 slow 的两倍：slow 走了 a+b，fast 走了 a+b 再加若干整圈。把两倍关系展开消项，得到 a 等于 c-b 加上若干整圈。

翻译成白话：从链表头再走 a 步会到达入口；而从相遇点出发走同样的 a 步，等于先补完这一圈剩下的 c-b 步回到入口、再原地绕几个整圈，落点还是入口。所以让一个新指针从头出发、slow 留在相遇点，两者同速各走一步，第一次相遇必然发生在环入口，返回那个节点即可。

复杂度与三个容易写错的地方

阶段一最多走 O(n) 步就会相遇或出局，阶段二再走头到入口的距离，总时间 O(n)；始终只用两三个指针，空间 O(1)。

易错点：一是循环条件必须同时判 fast 和 fast.next 非空，fast 一次跨两步，少判一个就会空指针崩溃；二是把相遇点当环入口直接返回，跳过了整个阶段二；三是阶段二的两个指针必须严格同速各走一步，上面的数学推导建立在同速之上，速度不一致就永远不会在入口相遇。