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

本文主要是介绍Floyd 循环检测算法(快慢指针法/龟兔指针法)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Floyd Cycle Detection Algorithm

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

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

在这里插入图片描述

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

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

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

这篇关于Floyd 循环检测算法(快慢指针法/龟兔指针法)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！