首页 > 代码库 > 判断单链表是否有环

判断单链表是否有环

判断单链表是否有环
假设两个指针分别为p1和p2,每循环一次只向前走一步,p2向前走两步,知道p2碰到NULL指针或者两个指针相等则说明有环
如果存在,start存放在圆环开始的节点
bool IsLoop(node *head,node *start)
{
node *p1=head,*p2=head;
if(head==NULL||head->next==NULL);//head为NULl或者链表为空
{
return false;
}
do
{
p1=p1->next;
p2=p2->next->next;//p2走两步 
}while(p2&&p2->next&&p1!=p2)
if(p1==p2)
{
*start=p1;//p1为圆环开始点
return true;
}
else
{
return false;
}
}
int main()
{
bool bLoop=false;
node *head=create();//create()函数的使用见我的博客(数据结构->单链表的创建)
node *start=head->next->next;
start->next=head->next;
node *loopstart=NULL;
bLoop=IsLoop(head,&loopstart);
printf("bloop=%d\n",bloop);
printf("bloop==loopstart?%d\n",(loopstart==start));
return 0;
}