判断一个单链表是否有环及环的链接点

《判断一个单链表是否有环及环的链接点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、给定一个单链表，只给出头指针h：1、如何判断是否存在环？2、如何知道环的长度？3、如何找出环的连接点在哪里？4、带环链表的长度是多少？解法：1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。2、对于问题2，记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度s。3、问题3：有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走

2、，相遇的那个点就是连接点。(证明在后面附注)4、问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度voidIsloop(Llinkhead){if(!head

3、

4、!head->next)return;Llinkp,q;boolloop=false;p=q=head->next;while(q&&q->next)//判断是否有环{p=p->next;q=q->next->next;if(p==q){loop=true;break;}}if(!loop)cout

5、<<"Thislinkhasnotloop";else{cout<<"Thislinkhasaloop";Llinkr=p;q=head->next;intnonloop=1,loopcount=1;//nonloop计算非环结点数，loopcount计算环上结点数do//计算环上的结点数{p=p->next;++loopcount;}while(p!=r);--loopcount;while(p!=q)//得到环的入口结点，同时计算得到非环的结点数{p=p->next;q=q->next;++

6、nonloop;}--nonloop;cout<<"Startofloop:"<data<

7、t->next)4{5slow=slow->next;6fast=fast->next->next;7if(slow==fast)break;8}9return!(fast==NULL

8、

9、fast->next==NULL);10}寻找环连接点（入口点）的程序：slist*FindLoopPort(slist*head)11{12slist*slow=head,*fast=head;13while(fast&&fast->next)14{15slow=slow->next;16fast=fast->nex

10、t->next;17if(slow==fast)break;1}2if(fast==NULL

11、

12、fast->next==NULL)3returnNULL;4slow=head;5while(slow!=fast)6{7slow=slow->next;8fast=fast->next;9}10returnslow;11}亦可以用类似与hash表的方法，即设立一个数组，将链表结点中的值做数组下标，当赋值冲突时就是环的接入点12boolisloop(Llinkp){if(!p

13、

14、!p->next)return

15、true;inta[MAXSIZE],n=0;memset(a,0,sizeof(int)*MAXSIZE);p=p->next;while(p){if(a[p->data]==-1)//存在环时，会发生冲突{cout<<"Loopnode:"<data<data]=-1;++n;p=p->next;}returnfalse;}LlinkCreatlinkLoop()1//创建一个有环的链表{Ll

16、inkhead=newLnode;//head->data=0;head->next=NULL;Lelemtypee;Llinkq=head;intN=0;cout<<"inputelems:";while(cin>>e){Llinkp=newLnode;++N;p->data=e;p->next=q->next;q->next=p;q=p;}cin.clear();cin.sync();srand(time(0));q->next=Fin