转载:http://www.cppblog.com/humanchao/archive/2008/04/17/47357.html
作者:胡满超 from:C++博客
有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。
问题:
1、如何判断一个链表是不是这类链表?
2、如果链表为存在环,如果找到环的入口点?
一、判断链表是否存在环,办法为:
设置两个指针(fast,
slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定
相遇。(当然,fast先行头到尾部为NULL,则为无环链表)程序如下:
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);
}
二、找到环的入口点
当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则
fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:
2s = s + nr
s= nr
设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r
+r = (n-1)r + L - a
a = (n-1)r + (L – a – x)
(L – a –
x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每
次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下:
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;
}
扩展问题:
判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。
比较好的方法有两个:
一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。
二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同
样的结尾点,则两个链表相交。
这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次
一步,相遇的第一点即为两个链表相交的第一个点。
分享到:
相关推荐
使用c语言中的循环链表及结构体实现约瑟夫环问题
通过循环链表实现约瑟夫环问题,用c语言实现。属于数据结构部分内容
循环链表实现约瑟夫环问题 约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又...
循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释
附件是使用双指针发判断链表有环的代码实现,在Java中,判断单链表是否有环的经典方法是使用Floyd的“龟兔赛跑”算法,也称为快慢指针法。这种方法利用两个指针,一个每次走一步(称为慢指针),另一个每次走两步...
自己写的链表,并用链表解决了约瑟夫环问题,大家给个意见,主要是链表
约瑟夫环问题的链表和数组两种解法 设有N个人围坐一圈并按顺时针方向从1到N编号,从第S个人开始进行1到M报数,报到第M个人时,此人出圈,再从他的下一个人重新开始1到M的报数,如此进行下去直到所有的人都出圈为止,...
用双向循环链表解决约瑟夫环问题的程序清单
这是用C写的链表表示的循环链表的程序。匹配的报告随后上传。
分别用数组和链表实现的约瑟夫环问题,内有详细的介绍。
这是用数组表示循环链表,解决约瑟夫环的问题。匹配的报告实验报告随后上传。
链表相关问题的完整代码,包括测试类和关键代码: **0、将链表翻转** **1、判断链表是否有环** **2、寻找环的入口点** **3、计算环的节点数** **4、计算(有环)链表的节点数** **5、找出环中距任意一点最远的节点** *...
约瑟夫环求解,循环链表的使用,经典问题
约瑟夫环 动态链表 处理 C
约瑟夫环 问题描述:约瑟夫问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到...
C++ 实现的约瑟夫环的操作,双向链表实现,适合初学者的了解双向链表
这是数据结构的约瑟夫双向链表算法,用c++做的,使我们学习数据结构的时候老师让我们做的实验,很经典,提供给大家参考一下!
本程序是采用带头结点的单向循环链表写成的,当指针指到要出列的结点时,先输出结点的序列号,再删除之,直到所有结点都出列完
如果 fast 指针到达链表的末尾(即 fast 或 fast.Next 为 nil),则说明链表中不存在环。 在 main 函数中,我们创建了一个有环的链表,并调用 hasCycle 函数来判断它是否有环,最后输出结果。 请注意,这个实现...
这里有两个资源,一个简易版的,一个扩展版(链表的增加、修改、查询、删除),还有论文(一个是约瑟夫环,一个是系数矩阵)。