菜鸟系列之C/C++经典试题(七)

阳光穿透心脏的1/2处 2022-08-12 00:07 156阅读 0赞

**找含单链表的环入口点**

问题1：如何判断单链表中是否存在环（即下图中从结点E到结点R组成的环）？

![SouthEast][]

分析：设一快一慢两个指针（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

有错误欢迎提出， 分享请标明出处， 谢谢！

感觉好的话就顶一个， 感觉不错的话就踩一个。

[SouthEast]: /images/20220810/9065b237b1f14418926004432b9c8fbe.png

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关菜鸟系列之C/C++经典试题(十)

打印1到最大的n位数题目：输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印1， 2， 3，…，999. 方法一：这道题一看感觉很简单，首先求的n位

本是古典何须时尚/ 2022年08月12日 00:21/ 0 赞/ 140 阅读

相关菜鸟系列之C/C++经典试题(九)

寻找数组中出现的唯一重复的一个数题目：1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次．每个数组元素只能访问一次，设计一个算法，将它找

你的名字/ 2022年08月12日 00:20/ 0 赞/ 37 阅读

相关菜鸟系列之C/C++经典试题(八)

计算二进制中1的个数题目：位运算方面的编程很少遇到，但也是很重的一个只是点，一个比较常见的题目就是计算一个数的二进制表示中的1的个数。分析：一个1都没有就是0，我们的

灰太狼/ 2022年08月12日 00:19/ 0 赞/ 162 阅读

相关菜鸟系列之C/C++经典试题(七)

找含单链表的环入口点问题1：如何判断单链表中是否存在环（即下图中从结点E到结点R组成的环）？ ![SouthEast][] 分析：设一快一慢两个指针（Node \

阳光穿透心脏的1/2处/ 2022年08月12日 00:07/ 0 赞/ 157 阅读

相关菜鸟系列之C/C++经典试题(六)

含有指针成员的类的拷贝题目：下面是一个数组类的声明与实现。请分析这个类有什么问题，并针对存在的问题提出几种解决方案。 template<typename T> c

淡淡的烟草味﹌/ 2022年08月11日 17:59/ 0 赞/ 148 阅读

相关菜鸟系列之C/C++经典试题(五)

求圆圈中剩下的最后一个数字题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字

超、凢脫俗/ 2022年08月11日 16:52/ 0 赞/ 141 阅读

相关菜鸟系列之C/C++经典试题(四)

题目一：查找最小的k个元素输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。分析：这道题最

你的名字/ 2022年08月11日 09:29/ 0 赞/ 172 阅读

相关菜鸟系列之C/C++经典试题(三)

设计包含min函数的栈题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。分析：这是200

墨蓝/ 2022年08月11日 05:30/ 0 赞/ 152 阅读

相关菜鸟系列之C/C++经典试题(二)

求子数组的最大和题目描述：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度

﹏ヽ暗。殇╰゛Y/ 2022年08月11日 05:30/ 0 赞/ 166 阅读

相关菜鸟系列之C/C++经典试题(一)

这个我写菜鸟系列之C/C++ 的第一篇文章题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。　　比如将二元

秒速五厘米/ 2022年08月11日 04:59/ 0 赞/ 217 阅读