首页 > 代码库 > 判断单链表是否有环
判断单链表是否有环
判断单链表是否有环
假设两个指针分别为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;
}
假设两个指针分别为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;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。