Title
Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
题目大意：判断一个链表是否为环，这个通过两个指针，一个快，一个慢，快的每次移动两步，慢的每次移动一步，当追上时，返回true
Solution
//cpp:
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* dummy=new ListNode(-1);
dummy->next=head;
ListNode *slow=dummy, *fast=dummy;
while(fast && fast->next){
slow=slow->next;
fast=fast->next-next;
if(slow==fast) return true;
}
return false;
}
};
也可以用set
/**
* 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)
{
unordered_set<ListNode*> set1;
while(head){
if(set1.find(head)!=set1.end()){
return true;
}else{
set1.insert(head);
}
head=head->next;
}
return false;
}
};