Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
分析
判断一个链表中是否有循环。一种方法是将链表指针依次保存在数组中，看下一个节点是否会在数组中出现，另一种方法是用两个指针，一个前进一步，另一个前进两步，如果存在循环，两个指针肯定有重合的时候。
/**
* 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;
}
