判断一个单链表是否有环及环的链接点(转)
给定一个单链表，只给出头指针h：
1、如何判断是否存在环？
2、如何知道环的长度？
3、如何找出环的连接点在哪里？
4、带环链表的长度是多少？
1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。
2、对于问题2，记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度s。
3、问题3：有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。(证明在后面附注)
4、问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度
void Isloop(Llink head)
&if(!head||!head-&next)
&Llink p,q;
&bool loop=
&p=q=head-&
&while(q&&q-&next)//判断是否有环
&&q=q-&next-&
&&if(p==q)
&if(!loop)
&&cout&&"This
link has not loop\n";
&&cout&&"This
link has a loop\n";
&&Llink r=p;
&&q=head-&
nonloop=1,loopcount=1;
//nonloop计算非环结点数，loopcount计算环上结点数
&&do//计算环上的结点数
&&}while(p!=r);
&&while(p!=q)//得到环的入口结点，同时计算得到非环的结点数
&&cout&&"\nStart
"&&p-&data&&&&
&&cout&&"\nCount
of nonloop: "&&nonloop
&&"\nCount of loop:
"&&loopcount
&&"\nCount of Linknode:
"&&nonloop+loopcount&&
判断是否存在环的程序：
bool&IsExitsLoop(slist&*head)&&
&&&&slist&*slow&=&head,&*fast&=&&&
&&&&while&(&fast&&&&fast-&next&)&&&
&&&&&&&&slow&=&slow-&&&
&&&&&&&&fast&=&fast-&next-&&&
&&&&&&&&if&(&slow&==&fast&)&break;&&
&&&&return&!(fast&==&NULL&||&fast-&next&==&NULL);&&
寻找环连接点（入口点）的程序：
slist*&FindLoopPort(slist&*head)&&
&&&&slist&*slow&=&head,&*fast&=&&&&&
&&&&while&(&fast&&&&fast-&next&)&&&
&&&&&&&&slow&=&slow-&&&
&&&&&&&&fast&=&fast-&next-&&&
&&&&&&&&if&(&slow&==&fast&)&break;&&
&&&&if&(fast&==&NULL&||&fast-&next&==&NULL)&&
&&&&&&&&return&NULL;&&
&&&&slow&=&&&
&&&&while&(slow&!=&fast)&&
&&&&&&&&&slow&=&slow-&&&
&&&&&&&&&fast&=&fast-&&&
&&&&return&&&
亦可以用类似与hash表的方法，即设立一个数组，将链表结点中的值做数组下标，当赋值冲突时就是环的接入点
isloop(Llink p)
&if(!p||!p-&next)
&int a[MAXSIZE],n=0;
&memset(a,0,sizeof(int)*MAXSIZE);
&&if(a[p-&data]==-1)//存在环时，会发生冲突
&&&cout&&"\nLoop
"&&p-&data&&endl
&&&&&&"\nLen
&&a[p-&data]=-1;
Llink CreatlinkLoop()
//创建一个有环的链表
&Llink head=new L
&//head-&data=0;
&head-&next=NULL;
&cout&&"input
&while(cin&&e)
&&Llink p=new L
&&p-&data=e;
&&p-&next=q-&
&&q-&next=p;
&cin.clear();
&cin.sync();
&srand(time(0));
&q-&next=Findnode(head,rand()%N);//随机产生环的接入点
Llink Findnode(Llink head,int n)//找出链表中的第n个结点
&Llink p=head-&
i=1;p&&i&n;++i)
////////////////////////////////////////////////////////
问题2的证明如下：
链表形状类似数字 6 。
假设甩尾（在环外）长度为 a（结点个数），环内长度为 b 。
则总长度（也是总结点数）为 a+b 。
从头开始，0 base 编号。
将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ...
当 i＜a 时，S(i)=i ；
当 i≥a 时，S(i)=a+(i-a)%b 。
分析追赶过程:
两个指针分别前进，假定经过 x 步后，碰撞。则有：S(x)=S(2x)
由环的周期性有：2x=tb+x 。得到 x=tb 。
另，碰撞时，必须在环内，不可能在甩尾段，有 x&=a 。
连接点为从起点走 a 步，即 S(a)。
S(a) = S(tb+a) = S(x+a)。
得到结论：从碰撞点 x 前进 a 步即为连接点。
根据假设易知 S(a-1) 在甩尾段，S(a) 在环上，而
S(x+a) 必然在环上。所以可以发生碰撞。
而，同为前进 a 步，同为连接点，所以必然发生碰撞。
综上，从 x
点和从起点同步前进，第一个碰撞点就是连接点。
/////////////////////////////////////////////////////////////
假设单链表的总长度为L，头结点到环入口的距离为a，环入口到快慢指针相遇的结点距离为x，环的长度为r，慢指针总共走了s步，则快指针走了2s步。另外，快指针要追上慢指针的话快指针至少要在环里面转了一圈多(假设转了n圈加x的距离)，得到以下关系：
2s = a + nr +
=&a = nr -
由上式可知：若在头结点和相遇结点分别设一指针，同步(单步)前进，则最后一定相遇在环入口结点，搞掂！
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。算法（82）
题目：如何判断一个单链表是否有环？若有环，如何找出环的入口节点。
一、单链表是否有环
思路分析：
单链表有环，是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点，这样在链表的尾部形成一个环形结构。判断链表是否有环，有以下几种方法。
typedef struct node
struct node *
（1）最常用方法：定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（next指向 NULL）都没有追上第一个指针，那么链表就不是环形链表。
bool IsLoop(NODE *head)
if (head == NULL)
return false;
NODE *slow = head-&
if (slow == NULL)
return false;
NODE *fast = slow-&
while (fast != NULL && slow != NULL)
if (fast == slow)
return true;
slow = slow-&
fast = fast-&
if (fast != NULL)
fast = fast-&
return false;
（2）通过使用STL库中的map表进行映射。首先定义 map&NODE *, int& 将一个 NODE * 指针映射成数组的下标，并赋值为一个 int 类型的数值。然后从链表的头指针开始往后遍历，每次遇到一个指针p，就判断 m[p] 是否为0。如果为0，则将m[p]赋值为1，表示该节点第一次访问；而如果m[p]的值为1，则说明这个节点已经被访问过一次了，于是就形成了环。
#include &iostream&
using namespace std;
#include &map&
map&NODE *, int&
bool IsLoop_2(NODE *head)
if (head == NULL)
return false;
if (m[p] == 0)
else if (m[p] == 1)
return true;
return false;
（3）不推荐使用：定义一个指针数组，初始化为空指针，从链表的头指针开始往后遍历，每次遇到一个指针就跟指针数组中的指针相比较，若没有找到相同的指针，说明这个节点是第一次访问，还没有形成环，将这个指针添加到指针数组中去。若在指针数组中找到了同样的指针，说明这个节点已经访问过了，于是就形成了环。
二、若单链表有环，如何找出环的入口节点。
&1& 定义两个指针p1和p2，在初始化时都指向链表的头节点。
&2& 如果链表中的环有n个节点，指针p1先在链表上向前移动n步。
&3& 然后指针p1和p2以相同的速度在链表上向前移动直到它们相遇。
&4& 它们相遇的节点就是环的入口节点。
那么如何得到环中的节点数目？可使用上述方法（1），即通过一快一慢两个指针来解决这个问题。当两个指针相遇时，表明链表中存在环。两个指针相遇的节点一定是在环中。可以从这个节点出发，一边继续向前移动一边计数，当再次回到这个节点时，即可得到环中的节点数了。
NODE *MeetingNode(NODE *head)
if (head == NULL)
return NULL;
NODE *slow = head-&
if (slow == NULL)
return NULL;
NODE *fast = slow-&
while (fast != NULL && slow != NULL)
if (fast == slow)
slow = slow-&
fast = fast-&
if (fast != NULL)
fast = fast-&
return NULL;
NODE *EntryNodeOfLoop(NODE *head)
NODE *meetingNode = MeetingNode(head);
if (meetingNode == NULL)
return NULL;
int count = 1;
NODE *p = meetingN
while (p != meetingNode)
for (int i = 0; i & i++)
while (q != p)
备注：在MeetingNode方法中，当快慢指针（slow、fast）相遇时，slow指针肯定没有遍历完链表，而fast指针已经在环内循环了n（n&=1）圈。假设slow指针走了s步，则fast指针走了2s步。同时，fast指针的步数还等于s加上在环上多转的n圈，设环长为r，则满足如下关系表达式：
所以可知：s =
假设链表的头节点到“环的尾节点“的长度为L（注意，L不一定是链表长度），环的入口节点与相遇点的距离为x，链表的头节点到环入口的距离为a，则满足如下关系表达式：
a + x = s =
可得：a + x = (n - 1)r + r = (n - 1)r + (L - a)
进一步得：a = (n - 1)r + (L -a - x)
(L - a -x)为相遇点到环入口节点的距离，即从相遇点开始向前移动(L -a -x)步后，会再次到达环入口节点。
&2& 从链表的头节点到环入口节点的距离 ＝ (n - 1) * 环内循环 ＋ 相遇点到环入口点的距离。
&3& 于是从链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：114716次
积分：2530
积分：2530
排名：第14254名
原创：135篇
转载：13篇
(6)(10)(27)(58)(47)本帖子已过去太久远了，不再提供回复功能。用C语言实现查询链表是否出现环_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
用C语言实现查询链表是否出现环
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用2下载券
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。问题：1、如何判断一个链表是不是这类链表？2、如果链表为存在环，如何找到环的入口点？
解答：一、判断单链表是否存在环，办法为：设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)程序如下：
1 bool IsExitsLoop(slist *head)
slist *slow = head, *fast =
while ( fast && fast-&next )
slow = slow-&
fast = fast-&next-&
if ( slow == fast ) break;
return !(fast == NULL || fast-&next == NULL);
当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1&=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：2s = s + nrs= nr设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。a + x = nra + x = (n & 1)r +r = (n-1)r + L - aa = (n-1)r + (L & a & x)(L & a & x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。程序描述如下：
1 slist* FindLoopPort(slist *head)
slist *slow = head, *fast =
while ( fast && fast-&next )
slow = slow-&
fast = fast-&next-&
if ( slow == fast ) break;
if (fast == NULL || fast-&next == NULL)
return NULL;
while (slow != fast)
slow = slow-&
fast = fast-&
判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。
比较好的方法有两个：1. 将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。2. 如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。
阅读(...) 评论()}