找含单链表的环入口点
问题1:如何判断单链表中是否存在环(即下图中从结点E到结点R组成的环)?
分析:设一快一慢两个指针(Node *fast, *low)同时从链表起点开始遍历,其中快指针每次移动长度为2,慢指针则为1。则若无环,开始遍历之后fast不可能与low重合,且fast或fast->next最终必然到达NULL;若有环,则fast必然不迟于low先进入环,且由于fast移动步长为2,low移动步长为1,则在low进入环后继续绕环遍历一周之前fast必然能与low重合(且必然是第一次重合)。于是函数可写如下:
bool hasCircle(Node* head, Node* &encounter)
{
Node *fast = head, *slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
encounter = fast;
return true;
}
}
encounter = NULL;
return false;
}
问题2:若存在环,如何找到环的入口点(即上图中的结点E)?
解答:如图中所示,设链起点到环入口点间的距离为x,环入口点到问题1中fast与low重合点的距离为y,又设在fast与low重合时fast已绕环n周(n>0),且此时low移动总长度为s,则fast移动总长度为2s,环的长度为r。则
s + nr = 2s,n>0 ①
s = x + y ②
由①式得s = nr
代入②式得
nr = x + y
x = nr - y ③
现让一指针p1从链表起点处开始遍历,指针p2从encounter处开始遍历,且p1和p2移动步长均为1。则当p1移动x步即到达环的入口点,由③式可知,此时p2也已移动x步即nr
- y步。由于p2是从encounter处开始移动,故p2移动nr步是移回到了encounter处,再退y步则是到了环的入口点。也即,当p1移动x步第一次到达环的入口点时,p2也恰好到达了该入口点。于是函数可写如下:
Node* findEntry(Node* head, Node* encounter)
{
Node *p1 = head, *p2 = encounter;
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
原文来自:http://blog.csdn.net/wuzhekai1985/article/details/6725263
有错误欢迎提出, 分享请标明出处, 谢谢!
感觉好的话就顶一个, 感觉不错的话就踩一个。
分享到:
相关推荐
C++/CLI教程C++/CLI教程C++/CLI教程C++/CLI教程C++/CLI教程C++/CLI教程
这年头,有个示例程序是多么的重要,节省了大量时间。
很好的,大家来看看 吧.初学的菜鸟来看看 吧其实我 是菜鸟啊啊
C/C++ threadpool封装, 线程池, Linux, 多线程, pthread
此程序使用的是#define创建的函数来作为储存的不可直接用于(if)判断
c++基础c++类,类的实例,类的指针,成员函数,构造函数.,适合新手菜鸟小白看,
使用的是C++编写的智能快递柜,无前端页面,只在工作台使用
RC4加密,想用的下吧,虽然是菜鸟,但觉得自己写的这个还不错
内存管理是C++最令人切齿痛恨的问题,也是C++最有争议的问题,C++高手从中获得了更好的性能,更大的自由,C++菜鸟的收获则是一遍一遍的检查代码和对C++的痛恨,但内存管理在C++中无处不在,内存泄漏几乎在每个C++...
c++ builder经典入门 对于刚接触的菜鸟来说非常有用
职场菜鸟需要注意的一些细节问题,一定会对你有所帮助!
c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮
同时标准化委员会声明就有的C++头文件将不再列于被支持的名单之中了,而旧有的C头文件为了满足“对C的兼容性”这个古老契约,仍然将继续存活下去。 但是,那些编译器厂商不可能去推翻他们客户的旧有编译器(也跟本...
c++基础知识 适合初学者 内容全面 菜鸟必看
菜鸟教程(Runoob)提供的免费网上编译器! 包含C++ C C# HTML/CSS/JavaScript PHP Python等许多语言的编译器! 还有画图 进制转换等常用工具! 还有资源共享! 欢迎来到(http://c.runoob.com)!
包含选择题,填空题以及上机操作题。比如 下述程序的输出结果是()。 int x = 10; y = x++; printf(“%d, %d”, (x++, y), y++); A、11, 10 B、11, 11 C、10, 10 D、10, 11 试卷考查应试者的c语言能力,
师兄推荐的研究生找工作前必看的书。教你如何从菜鸟进化为编程高手。
这是本人刚入职作的作业,因为刚毕业,所以写的代码基本不能看,也希望各位能点评一下,自己刚学习,哎,还有好多考虑到,希望大家可以帮我找下bug和优化下代码,谢谢了! 自己是刚毕业工作的学生,所以写得很laji...
我们大学上课老师的讲课内容。。。 我们老师很牛逼,觉得清华教材讲的很深,不利于全然不会的弱弱弱菜鸟学习。。 便,自创C++教材,,,供我们学习~ *注意:要有C语言基础*
c语言菜鸟必看代码c语言菜鸟必看c语言菜鸟必看代码代码