判断单链表是否存在回环原理很简单,即假设有两个指针p1,p2。在每次循环的时候,p1先走一步,p2走两步,直到p2碰到空指针或两者相等时循环结束,如果两个指针相等则说明存在回环。
具体代码如下:(仅供参考)
#include <iostream>
using namespace std;
#include <stdio.h>
struct Node
{
int data;
Node *next;
};
Node *create()
{
Node *head;
int data=0;
int i=0,j=0;
Node *New;
Node *q;
head=(Node*)malloc(sizeof(Node));
while(1)
{
cout<<"input the "<<(++i)<<"th "<<"data: ";
cin>>data;
if(data==0)
{
break;
}
New=(Node *)malloc(sizeof(Node));
New->data=data;
if(++j==1)
{
head->next=New;
}
else
{
q->next=New;
}
q=New;
}
New->next=NULL;
return head;
}
int length(Node *head)
{
Node *p;
int len=0;
p=head->next;
if(head->next==NULL)
return 0;
while(p!=NULL)
{
len++;
p=p->next;
}
return len;
}
void print(Node *head)
{
Node *p=head ;
int i=0;
if(head->next==NULL)
return ;
while(p->next!=NULL)
{
p=p->next;
cout<<"The "<<++i<<"th data is: "<<p->data<<endl;
}
cout<<endl;
}
//判断是否存在回环
//如果存在,start存放回环开始节点
bool IsLoopList(Node *head,Node **start)
{
Node *p1=head,*p2=head;
if(head==NULL && head->next==NULL)
{
return false;
}
do
{
p1=p1->next; //p1走一步
p2=p2->next->next;//p2走两步
}while(p2 && p2->next && p1!=p2);
if(p1==p2)
{
*start=p1;//p1为回环开始节点
return true;
}
else
return false;
}
int main()
{
Node *head;
head=create();
print(head);
cout<<"The length of List is: "<<length(head)<<endl;
bool IsLoop=false;
Node *start=head->next->next->next->next;//使第四个节点为回环开始位置
start->next=head->next;//回环连接到第二个节点
Node *loopStart=NULL;
IsLoop=IsLoopList(head,&loopStart);
cout<<"IsLoop="<<IsLoop<<endl;
cout<<"IsbLoop==loopStart? "<<(loopStart==start)<<endl<<endl;
return 0;
}
在上面主函数的情况下,手动设置了第四个节点为回环的开始位置,并将回环爱你接到第二个节点。最后的输出均为1,表明存在回环。
运行结果如下:
将主函数中
start->next=head->next;//回环连接到第二个节点
注释掉的话,,最后的输出结果均为0,表明不存在回环。输出结果如下:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)