追击问题大家都知道,是一个算速度差以及距离差的小学题目
速度差×追及时间=追及路程
路程差÷速度差=追及时间
Floyd判圈算法是一个可以在有限状态机、迭代函数或者链表上判断是否存在环,求出该环的起点与长度的算法
如果有限状态机、迭代函数或者链表上存在环,那么在某个环上以不同速度前进的2个指针必定会在某个时刻相遇。同时显然地,如果从同一个起点(即使这个起点不在某个环上)同时开始以不同速度前进的2个指针最终相遇,那么可以判定存在一个环,且可以求出2者相遇处所在的环的起点与长度
设有两个指针同时从链表起点(即点A处)同时前移,快指针fast每次挪动两格,慢指针slow每次挪动一格
一、证明假如有环,两指针必相遇
虽然看起来仿佛是个这还用证的问题,但还是说一下
因为快指针fast移动速度是慢指针slow的两倍,当慢指针slow从起点A运动到环起点B的时候。这时快指针fast在环内,慢指针slow在环起点,实际追击距离为
快指针fast必能追上慢指针slow并且是在一圈内追上
二、如何求环长
设点C为两指针相遇点
将慢指针slow从相遇节点开始继续后移,快指针fast不动,当两指针再次相遇时,慢指针slow移动的距离即为环长l
三、环起点的求法及原理
为了求出环的起点,只要令慢指针slow仍均位于节点C,而令快指针fast返回起点节点A,此时fast与slow之间距为环长度l的整数倍。随后,同时让fast和slow往前推进,且保持二者的速度相同:fast每前进1步,slow前进1步。持续该过程直至fast与slow再一次相遇,设此次相遇时位于同一节点B,则节点B即为从节点A出发所到达的环的第一个节点,即环的一个起点
设其中AB距离为m,BC距离为k,环长为l
由此可知慢指针slow的位移是环长l的整数倍
起点A到环起点B距离m等于环的整数倍外加一段弧长,每次挪1步,必会在点B相遇