前言
该算法用于寻找链表中环的入口以及环的长度,在算法竞赛中可用于寻找序列的循环节。
算法推导
设定两个指针tortoise和hare,一开始都在起点,每次tortoise移动1步,hare移动2步。
当tortoise走到环入口时,hare早已处在环内。设从起点到环入口的距离为 T,从环入口到hare为 r,环的周长为 c。由于hare的移动速度为tortoise的两倍,可得等式 2T=T+r+kc,化简得 T=r+kc,其中 k\in \mathbb{N} 为hare已经转过的环数。
若hare想追上tortoise,则hare需要再走 2(c-r) 步才能追上,此时tortoise也走了 c-r 步。若从相遇点再往前走 r 步,就到了环的入口处。
在hare与tortoise第一次相遇的时候,将hare放回起点,tortoise不动,然后让它们以相同速度移动,由等式 T=r+kc 可得,当它们第二次相遇时,相遇点一定在环入口处。这样就找到了环的入口。
此时让tortoise停下,hare继续跑,当它们第三次相遇时,hare刚刚走过的路程即为环的长度 c。
khnb!