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/