还记得这道题的[第一个版本](../07. Linked List Cycle)吗?
当时为了给 @Mooophy 解释,我还列了个式子。假设 slow 和 fast 在走了x步后相遇,此刻:
- slow 走了 x 步
- fast 走了 2x+1 步 (因为一开始 fast 就领先一步)
由于相遇,所以 fast - slow = x+1 = 一圈的步长。假设进入圈需要 m 步。那么
- slow 在圈内走了 x-m 步
- slow 还需要走个 (x+1) - (x-m) = m+1 步,才能再次到达圈的入口
咦,m+1 里面的 m 不就是从开始入圈所需要的步数吗?假设 head 从头开始走,让 slow 再走一步。
那么 m 步之后,head 和 slow 将同时到达圈的入口!!!
这个入口不就是返回值吗?
这道题真的是太奇妙了,我仅仅是稍稍改了一下第一版的程序,就 AC 了。
为了不破坏原来的链表,我用废弃的 fast 顶替了 head。
经 @Mooophy 点拨,这里的 head 其实是以传值的方式传入的,所以我不会破坏原来的链表,早上糊涂了。
直接使用 head ,代码更加的直观易懂,就像一场接力赛,head 觉得 slow 太慢了,从原点出发接力 slow.
不过,他并不知道,自己那速度,也赶不上 fast 啊,哈哈。