floyd’s cycle detecion
为什么找出环的算法是使用快慢指针呢,以下做了简单的推导
如图所示,假设从环的起点到环的入口点的距离为m, 快慢指针的相遇点的距离据入口点的距离为k。
环的长度设置为l
则有dist_fast = m + p l + k,此为快指针行走的距离,也就是起点到入口点的距离 + 任意圈数(p圈)的环的长度 + 快慢指针相遇的点到入口的距离k。
同理dist_slow = m + q l + k。 dist_fast = dist_slow 2 (因为快指针速度是慢指针两倍)。 推导则有 l (p-2q) = m + k
p-2q是一个整数,l * int = m + k, 因此当找到了相遇点之后, 快指针从起点开始,每次移动一步,慢指针从相遇点开始,每次移动一步。快指针移动m步时,慢指针也移动了m步,此时刚好等于一个环的长度的整数倍,因此也就是环的入口点。