https://leetcode-cn.com/problems/linked-list-cycle/
給定一個鏈表绽左，判斷鏈表中是否有環(huán)桦踊。
為了表示給定鏈表中的環(huán)筷厘，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）幻捏。 如果 pos 是 -1，則在該鏈表中沒有環(huán)殿遂。
/**
* 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) {
map<ListNode*,int> ma;
while(head!=NULL){
if(ma[head]!=1){
ma[head]=1;
head=head->next;
}
else{
return true;
}
}
return false;
}
};
改進(jìn)：使用快慢指針诈铛，若指針相遇則判斷有環(huán)
/**
* 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)
return false;
ListNode *p1=head,*p2=head->next;
while(p1!=p2){
if(p2==NULL||p2->next==NULL)
return false;
p1=p1->next;
p2=(p2->next)->next;
}
return true;
}
}; 