P94. 单链表中圆环的开始节点

https://algocasts.io/episodes/nwp85DW7

请问a + kd + b 为什么等于 2a? 我理解如果是slow第一圈都没走完,不应该是2(a + b)? 导出a = kd - b.
也就意味着当slow和fast在第一次环内相遇后,从head出发一个新的new,从相遇点slow继续走,new和slow一定相遇在环的初始点。
油管上,看了这个思路:假设slow,fast各转了x,y圈
第一次相遇时,
slow: a + xCycle + b, fast = a + yCycle + b => 2(a + xCycle + b) = a + yCycle + b
也就是 a = (x+y)Cycle - b; 结论和上面的一样,也就是只要从head出发一个new,同时slow从slow,fast在cycle里相遇的点出发,无论转了几圈,最后都相遇在环的初始点。
谢谢
油管那个链接是这个:

@ky

a+kb+d=2a ,此时慢指针刚到环入口,于是走的距离是 a。a+kb+d 是快指针走的,意思是走了环外 a,以及 k 圈环(周长为 b),k 圈后停在离环入口 d 处。快指针速度是慢指针 2 倍,因此它走的距离也是它的 2 倍。于是有 a+kb+d=2a

你再把讲解部分的视频看一看,我觉得讲得挺清楚的。油管上的分析我没看,但应该是用的另一种思路,得出同样的结果。

P.S. 写帖子时,可以用 markdown 语法,这样可以让排版好看一些。

我觉得另一种思路更简单直接一些,并且更「符合代码」。

首先让快慢指针相遇,假设 相遇的地点在距离环入口为 d 处,这时有:

  1. 慢指针走了 a+d
  2. 快指针走了 a+kb+d

快指针是慢指针的两倍,因此 a+kb+d=2(a+d) 即 a=kb-d
此时慢指针距离环入口还有 b-d

如果这时候放一个和慢指针相同速度的 p 于起点,想让它和慢指针相遇,此时

  1. p指针到环入口是 kb-d
  2. 慢指针到环入口是 b-d

它们距离环入口的距离是 b 的整数倍,因此 p 和慢指针的交点即为环入口。

1赞

@singee

:+1: