判断链表是不是有环以及环的入口点(转载) 留个记号_读书人
判断链表是不是有环以及环的入口点(转载) 留个记号
&来源：读书人网&【读书人网(Reader8.cn)：综合教育门户网站】
判断链表是否有环以及环的入口点(转载) 留个记号有几种解法：1. 遍历链表，将已经遍历过的节点放在一个hash
判断链表是否有环以及环的入口点(转载) 留个记号 有几种解法：1. 遍历链表，将已经遍历过的节点放在一个hash表中，如果一个节点已经存在hash表中，说明有环。时间:O(n) 空间:O(n) 2. 反转链表 时间O(n)，空间O(1),使用三个指针 3. 快慢指针。 时间O(n), 空间O(1),使用两个指针 参考：http://kb.cnblogs.com/page/52054/http://www.cnblogs.com/shawn-zhou/archive//1341307.htmlhttp://kb.cnblogs.com/page/52054/[url]http://keep.javaeye.com/blog/293454 [/url]【摘要】有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。1、如何判断一 个链表是不是这类链表？2、如果链表为存在环，如果找到环的入口点？扩展：判断两个单链表是否相交，如果相交，给出相交的第一个点。有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。问题：1、如何判断一个链表是不是这类链表？2、如果链表为存在环，如果找到环的入口点？ 解答：一、判断链表是否存在环，办法为： 设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)程序如下：bool IsExitsLoop(slist * head){slist * slow = head ,
fast -& next ) {slow
slow -&fast
fast -& next -&if
fast -& next
二、找到环的入口点当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 C 1)r +r = (n-1)r + L - aa = (n-1)r + (L C a C x)(L C a C x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。程序描述如下：slist *
FindLoopPort(slist * head){slist * slow
fast -& next ) {slow
slow -&fast
fast -& next -&if
fast -& next
fast){slow
slow -&fast
附一种易于理解的解释： 一种O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）： 关于这个解法最形象的比喻就是在操场当中跑步，速度快的会把速度慢的扣圈可以证明，p2追赶上p1的时候，p1一定还没有走完一遍环路，p2也不会跨越p1多圈才追上我们可以从p2和p1的位置差距来证明，p2一定会赶上p1但是不会跳过p1的因为p2每次走2步，而p1走一步，所以他们之间的差距是一步一步的缩小，4，3，2，1，0 到0的时候就重合了根据这个方式，可以证明，p2每次走三步以上，并不总能加快检测的速度，反而有可能判别不出有环既然能够判断出是否是有环路，那改如何找到这个环路的入口呢？ 解法如下： 当p2按照每次2步，p1每次一步的方式走，发现p2和p1重合，确定了单向链表有环路了接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当p1和p2再次相遇的时候，就是环路的入口了。这点可以证明的：在p2和p1相遇的时候，假定p1走了n步骤，环路的入口是在p步的时候经过的，那么有p1走的路径： p+c ＝ n；&&&&&&&& c为p1和p2相交点，距离环路入口的距离p2走的路径： p+c+k*L = 2*n；&& L为环路的周长，k是整数显然，如果从p+c点开始，p1再走n步骤的话，还可以回到p+c这个点同时p2从头开始走的话，经过n步，也会达到p+c这点显然在这个步骤当中p1和p2只有前p步骤走的路径不同，所以当p1和p2再次重合的时候，必然是在链表的环路入口点上。
扩展问题：判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。比较好的方法有两个：一、将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。二、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。判断链表是否有环 找到环的入口节点_百度知道
判断链表是否有环 找到环的入口节点
我有更好的答案
在单向链表中，在单链表中设置头节点的作用是（简化插入、删除操作 ），除首节点外，任何一个节点的存储位置由（前驱节点的后继指针 ）表示。
采纳率：94%
来自团队：
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。判断一个单链表是否有环及环的链接点(转)
给定一个单链表，只给出头指针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 -
由上式可知：若在头结点和相遇结点分别设一指针，同步(单步)前进，则最后一定相遇在环入口结点，搞掂！
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。看了书上的讲解，关于得出环的入口点的计算公式着实挺难理解，而且又没有配图，网上看到的几篇博客大多照搬书上的讲解。我在理解了思想之后尝试用自己的语言表达一下我的解法思路，很简单。
判断单链表是否有环
这是很多公司入门级的面试笔试题。单链表由于每个结点只有一个next指针指向下一个结点，不存在其他指针，所以一旦进入环里，就再也出不去了。类似于下图（像一个烤盘）
那么怎么样判断单链表是否有环呢？方法很简单，把环看作操场，两位选手在操场上赛跑，一个速度快，一个速度慢，如果他们一直跑，快的选手肯定会在第一次超过慢的选手之后再次追上慢的选手，与他相遇；若现在没有环，那么快的选手将始终跑在慢的选手前面，不可能有第二次相遇。所以我们判断一个链表是否有环的方法就是基于这个思想：
在链表头部设两个指针，一个每次向后移动两个位置（快指针），另一个每次向后移动一个位置（慢指针）。这相当于在起点设置了两位跑步选手，跑的快的选手的速度是慢的选手的两倍。接下来两个指针在遍历链表过程中，如果快指针到达链表尾还没有和慢指针相遇，说明链表无环，反之说明有环。
获得环的入口点
书上说的公式挺复杂的，我们这里只要考虑两个指针第一次相遇的情况就好了。第一次相遇的条件是：快指针在环内比慢指针多走了一圈。如下图所示，两个指针从起点O出发，在环中的B点相遇，现在我们的目标是如何根据B点找到A点这个结点。注意：结点在环中的前进方向是顺时针，即A→B→A.
毫无疑问，两个指针第一次在B点相遇时：
慢指针走过的路程是：
S_slow = |OA| +|AB| = x + y.
快指针走过的路程是：
|OA| + |AB| + |BA| + |AB| = x + y + z + y.
又因为快指针的速度是慢指针的两倍，所以在相同时间内快指针走过的路程是慢指针的两倍，所以
S_fast = 2 * S_slow
2(x + y) = x + y + z + y.
|BA| = |OA|.
所以在两个指针相遇后，将慢指针移到O点起始位置，即链表头指针位置，快指针仍然在B点。然后它们一起向前移动，每次移动一个位置，由于|BA| = |OA|, 所以他们最终肯定会在A点相遇，A点这个相遇点就是环的入口点。
代码很简单，就不贴了。博主最新文章
博主热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)}