1.題目
2.思路
有點像小學數學的追及問題：若鏈表存在環，快指標每次走2步，而慢指標每次走1步，那么快指標一開始肯定比慢指標快2倍距離，而有環的話快指標優先進入環，又因為慢指標也進入環時，兩個指標每次運動就會使距離減1，逐漸相遇，
拓展：
判斷環的長度——快慢指標相遇后繼續移動，直到第二次相遇，兩次相遇之間的移動次數即為環的長度，
題目的pos不作為引數傳遞，只是便于給出的樣例解釋，
3.代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL || head->next==NULL){
return false;
}
ListNode* fast=head;
ListNode* slow=head;
while(fast!=NULL && fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
if(fast==slow){
return true;
}
}
return false;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257369.html
標籤：其他
上一篇：MFC學習筆記