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.环的长度。
当快慢两指针相遇的时候,令快指针不动、慢指针继续前进,当再次相遇时,所走的步数就是环的长度。
给你一个链表的头节点 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; } };