先说结论:
- 用两个指针 first,second 分别从起点开始走,first 每次走一步,second 每次走两步。
- 如果过程中 second 走到null,则说明不存在环。否则当 first 和 second 相遇后,让 first 返回起点, second待在原地不动, 然后两个指针每次分别走一步, 当相遇时, 相遇点就是环的入口。
证明:
如上图所示,a 是起点,b 是环的入口,c 是两个指针的第一次相遇点,ab 之间的距离是 x,bc 之间的距离是 y。(在环中顺时针走)
0x01 证明1 - 公式推导
用 z 表示从 c 点顺时针走到 b 的距离。则第一次相遇时 second 所走的距离是 $x+n*(y+z)+y$,n 表示圈数,first 所走的距离是 $x + y$,同时 second 走过的距离是 first 的两倍,所以有等式 $x+n*(y+z)+y=2*(x+y)$,得出 $x=(n−1)×(y+z)+z$(即 x 表示的是 c 点顺时针走到 b 的距离 + $n-1$ 圈)。那么此时(相遇时)我们让 second 从 c 点开始走,走 x 步,会恰好走到 b 点;而让 first 从 a 点开始走,走 x 步,也会走到 b 点。
0x02 证明2 - 逻辑推理
当 first 走到 b 时,由于 second 比 first 多走一倍的路,所以 second 已经从 b 开始在环上走了 x 步,此时距离 b 还差 y 步(这是因为第一次相遇点在 b 之后 y 步,在相遇点这个时刻,我们让 first 退回到 b 点,即退了y步,则 second 会退 2y 步,首先退 y 步到b点,然后再退 y 步,也就是距离 b 点差 y 步);所以 second 从 b 点走 x+y 步即可回到 b 点,所以 second 从 c 点开始走,走 x 步即可恰好走到 b 点,同时让 first 从头开始走,走 x 步也恰好可以走到 b 点。所以第二次相遇点就是 b 点。
- - - 结束 - - -