Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
分析
判斷一個(gè)鏈表中是否有循環(huán)执桌。一種方法是將鏈表指針依次保存在數(shù)組中窄俏，看下一個(gè)節(jié)點(diǎn)是否會(huì)在數(shù)組中出現(xiàn)，另一種方法是用兩個(gè)指針诲祸，一個(gè)前進(jìn)一步啦鸣，另一個(gè)前進(jìn)兩步盈简，如果存在循環(huán)碑诉，兩個(gè)指針肯定有重合的時(shí)候。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode *array[100000];
int num=0;
struct ListNode *p=head;
while(p!=NULL)
{
for(int i=0;i<num;i++)
{
if(p==array[i])
return true;
}
array[num]=p;
num++;
p=p->next;
}
return false;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
if(head==NULL)
return false;
struct ListNode *p1=head,*p2=head->next;
while(p1!=NULL&&p2!=NULL)
{
if(p1==p2)
return true;
p1=p1->next;
if(p2->next!=NULL)
p2=p2->next->next;
else
p2=p2->next;
}
return false;
}
