首页 > 代码库 > 判断单链表是否有环相关问题（转载加总结）
判断单链表是否有环相关问题（转载加总结）
给定一个单链表，只给出头指针h：
1、如何判断是否存在环？
2、如何知道环的长度？
3、如何找出环的连接点在哪里？
4、带环链表的长度是多少？
解法：
1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。
2、对于问题2，记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度s。
3、问题3：有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。
设环的周长为r，环外的长度为l，分l<=r,和l>r考虑，容易得出结论。
4、问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度。
代码是直接copy：
void Isloop(Llink head){ if(!head||!head->next) return; Llink p,q; bool loop=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<<"This link has not loop\n"; else { cout<<"This link has a loop\n"; Llink r=p; q=head->next; int nonloop=1,loopcount=1; //nonloop计算非环结点数，loopcount计算环上结点数 do//计算环上的结点数 { p=p->next; ++loopcount; }while(p!=r); --loopcount; while(p!=q)//得到环的入口结点，同时计算得到非环的结点数 { p=p->next; q=q->next; ++nonloop; } --nonloop; cout<<"\nStart of loop: "<<p->data<<endl; cout<<"\nCount of nonloop: "<<nonloop <<"\nCount of loop: "<<loopcount <<"\nCount of Linknode: "<<nonloop+loopcount<<endl; }} 判断是否存在环的程序：bool IsExitsLoop(slist *head) { slist *slow = head, *fast = head; while ( fast && fast->next ) { slow = slow->next; fast = fast->next->next; if ( slow == fast ) break; } return !(fast == NULL || fast->next == NULL); } 寻找环连接点（入口点）的程序：slist* FindLoopPort(slist *head) { slist *slow = head, *fast = head; while ( fast && fast->next ) { slow = slow->next; fast = fast->next->next; if ( slow == fast ) break; } if (fast == NULL || fast->next == NULL) return NULL; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } 亦可以用类似与hash表的方法，即设立一个数组，将链表结点中的值做数组下标，当赋值冲突时就是环的接入点 bool isloop(Llink p){ if(!p||!p->next) return true; int a[MAXSIZE],n=0; memset(a,0,sizeof(int)*MAXSIZE); p=p->next; while(p) { if(a[p->data]==-1)//存在环时，会发生冲突 { cout<<"\nLoop node: "<<p->data<<endl <<"\nLen of node: "<<n<<endl; return true; } a[p->data]=-1; ++n; p=p->next; } return false;}Llink CreatlinkLoop()//创建一个有环的链表{ Llink head=new Lnode; //head->data=http://www.mamicode.com/0; head->next=NULL; Lelemtype e; Llink q=head; int N=0; cout<<"input elems:"; while(cin>>e) { Llink p=new Lnode; ++N; p->data=http://www.mamicode.com/e; p->next=q->next; q->next=p; q=p; } cin.clear(); cin.sync(); srand(time(0)); q->next=Findnode(head,rand()%N);//随机产生环的接入点 return head;}Llink Findnode(Llink head,int n)//找出链表中的第n个结点{ if(n<=0) return head; Llink p=head->next; for(int i=1;p&&i<n;++i) p=p->next; return p;}
扩展问题：
判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。
比较好的方法有两个：
一、将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。
二、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点（由于是单链表，每个节点后面不会有两个节点，也不会存在一条链的头部与另一条的尾部相交的情况），我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。
这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。