养心殿
0%

龟兔赛跑

发表于 更新于

Floyd判圈算法即龟兔赛跑算法

​ 假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

力扣141.环形链表给你一个链表的头节点head，判断链表中是否有环。若链表中存在环，则返回true，否则返回false。

解：

​ 定义快慢两个指针，慢指针每次移动一步，快指针每次移动两步。初始时，慢指针位于head处，快指针位于head->next处。在移动过程中，快指针追上满指针，则有环，否则快指针到达链表尾部，则无环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
    public:
    	bool hasCycle(ListNode* head){
            if(head == nullptr || head->next == nullptr)
                return false;
            ListNode* slow = head;
            ListNode* fast = head->next;
            while(slow!=fase)
            {
                if(fast==nullptr||fast->next==nullptr)
                    return false;
                
                slow = slow->next;
                fast = fast->next->next;
            }
            return true;
        }
};

https://leetcode.cn/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/