弗洛伊德判环算法
m为环外路径,n为环的长度
慢
m+kn
快:慢的两倍
m+m+2kn
快-慢:快慢相遇,所以快比慢多跑t圈
m+kn=tn
此时慢从头开始,走m步到达起点,快也走m步:
2m+2kn+m=m+2tn
所以此时快指针的位置是环起点后转了2t圈,所以又回到了环起点。
m为环外路径,n为环的长度
慢
m+kn
快:慢的两倍
m+m+2kn
快-慢:快慢相遇,所以快比慢多跑t圈
m+kn=tn
此时慢从头开始,走m步到达起点,快也走m步:
2m+2kn+m=m+2tn
所以此时快指针的位置是环起点后转了2t圈,所以又回到了环起点。
相关推荐