MENU

【快慢指针】找链表中环的入口节点

October 11, 2020 • Read: 2230 • 编程之路,Algorithm

先说结论:

  1. 用两个指针 first,second 分别从起点开始走,first 每次走一步,second 每次走两步
  2. 如果过程中 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 点。

- - - 结束 - - -
  • 文章标题:【快慢指针】找链表中环的入口节点
  • 文章链接:https://blog.canye365.cn/archives/290.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: February 9, 2021