Floyd龟兔算法

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

Floyd龟兔算法

算法描述

Floyd龟兔算法是一种指针算法。该算法仅使用移动速度不同的两个指针就能检测出是否有环。Floyd龟兔算法解决以下问题：
1.检测是否有环。
想象在一个环形跑道上跑步，两个人同时出发，出发以后速度快的人终究会在某一点和速度慢的人相遇。一般这个时候相遇，速度快的人比速度慢的人至少多跑一圈。

2.环的起点节点。
如上图，h表示快指针，t表示慢指针，两者相遇在M点。
令h仍位于节点M，令t返回起始节点S。随后，同时让t和h往前推进，且保持两者速度相同：t前进一步，h前进一步，持续该过程直至t与h再一次相遇，则两者相遇在环的一个起点。
证明：
t走的步数，step = p + m + a * C，a表示相遇时t走的圈数
h走的步数，2 * step = p + m + b * C，b表示相遇时h走的圈数
两者相减：step = (b - a) * C = p + m + a * C，由此可知t走的步数是环C的倍数，即 p + m 刚好是环长度C的倍数。

调整h速度行进后，t走了p步到达P，h从M处出发走了p步，相对于环起始位置，h走过的距离是 m + p，而m + p刚好是环长度C的倍数，即h此时也位于环起始节点处，即t和h在P处相遇。

3.环的长度。
当快慢两指针相遇的时候，令快指针不动、慢指针继续前进，当再次相遇时，所走的步数就是环的长度。

141.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

class Solution {
public:
    bool hasCycle(ListNode *head) {
       if(head == NULL || head->next == NULL)   return false; // 使用指针一定要注意next是否存在
       ListNode * fastPoint = head->next->next;
       ListNode * slowPoint = head->next;
       if(fastPoint == slowPoint)   return true;
       while(fastPoint != NULL && slowPoint != NULL && fastPoint != slowPoint){
           if(fastPoint->next == NULL)   return false; //在使用快慢指针的时候，要注意快指针是否会浮空  即若next == NULL 则 next->next (浮空)
           fastPoint = fastPoint->next->next;  slowPoint = slowPoint->next;
           if(fastPoint == slowPoint)   return true;
       }
       return false;
    }
};

这篇关于Floyd龟兔算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！