【学习笔记】环检测算法 Floyd's Tortoise and Hare

前言

该算法用于寻找链表中环的入口以及环的长度,在算法竞赛中可用于寻找序列的循环节。

算法推导

设定两个指针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

点赞
  1. iNx说道:

    khnb!

发表评论

电子邮件地址不会被公开。必填项已用 * 标注