Skip to content

Latest commit

 

History

History
 
 

141. Linked List Cycle II

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

还记得这道题的[第一个版本](../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 啊,哈哈。