1. 题目
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
2.解决方案
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head){
return false;
}
ListNode* slowPoint = head;
ListNode* fastPoint = head;
while(slowPoint->next){
//slow point move one step
slowPoint = slowPoint->next;
//fast point move two step
if(fastPoint->next){
fastPoint = fastPoint->next;
}else{
return false;
}
if(fastPoint->next){
fastPoint = fastPoint->next;
}else{
return false;
}
if(slowPoint->val == fastPoint->val){
return true;
}
}
return false;
}
};
思路：用快慢指针来走，如果有环的话，1定会遇到1起。
http://www.waitingfy.com/archives/1591