leetcode141-环形链表
其算法应用龟兔赛跑的思想，使用一个slow和fast指针初始都指向链表第一个节点，slow每次向前走一步，fast向前走两步。如果链表无环，那么fast会先走到NULL节点。如果有环，那么当slow和fast都进入环的时候，由于fast比slow走的快，fast总会追上slow。C++代码如下：
写法一:快慢指针不在同一起点
/**
* 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* slow=head,*fast=head->next;
while(fast!=NULL && fast->next!=NULL){
if(slow==fast)
return true;
else{
slow=slow->next;
fast=fast->next->next;
}
}
return false;
}
};
写法二:快慢指针在同一起点
/**
* 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* slow=head,*fast=head;
while(true){ //把跳出循环的逻辑写在循环体内部会简单一点
slow=slow->next;
fast=fast->next;
if(fast==NULL)
return false;
fast=fast->next;
if(fast==NULL)
return false;
if(slow==fast)
return true;
}
return false;
}
};
注意要判断两次fast是否为空.