Floyd循环检测算法(快慢指针法/龟兔指针法)

博客 分享
0 203
优雅殿下
优雅殿下 2022-01-28 01:54:37
悬赏:0 积分 收藏

Floyd 循环检测算法(快慢指针法/龟兔指针法)

Floyd Cycle Detection Algorithm

??Floyd Cycle Detection Algorithm,即 Floyd 循环检测算法,又称快慢指针法、龟兔指针法。该算法用于判断链表是否存在环,以及判断环的起点与长度的算法。

算法原理

??该算法基于两个指针,从头开始遍历,一个指针跑得快,另一个指针跑得慢,其中快指针的速度是慢指针的2倍。只要存在环,无论快慢指针从哪里开始,那么快慢指针最终一定会相遇,因为快指针没走一次,都会向慢指针靠近一个节点。

在这里插入图片描述

算法应用

判断是否有环

??如果存在环,快慢指针必定相遇,反之,如果慢指针走到结尾还没相遇则不存在环。

求环的长度

??假设存在环,那么快慢指针必定相遇,假设快慢指针在 X 点第一次相遇,此时再让两指针前进,下次相遇时快指针比慢指针多走了一圈,由此即可计算出环长度。

求环的起点

??当快慢指针第一次相遇后,将慢指针指向头节点,快指针指向相遇点的下一个节点。再次让快慢指针运动,当快慢指针再次相遇时,相遇点即为环的第一个节点。

posted @ 2022-01-28 01:46 Acx7 阅读(0) 评论(0) 编辑 收藏 举报
回帖
    优雅殿下

    优雅殿下 (王者 段位)

    2018 积分 (2)粉丝 (47)源码

    小小码农,大大世界

     

    温馨提示

    亦奇源码

    最新会员