题目:
给定一个单链表,只给出头指针head:
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中求出的环的长度,二者之和就是带环单链表的长度
判断是否存在环的程序:
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);
}
寻找环连接点(入口点)的程序:
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;
}
亦可以用类似与hash表的方法,即设立一个数组,将链表结点中的值做数组下标,当赋值冲突时就是环的接入点
证明题:
对于一个顺时针的环,有P,Q两点,且两点相距为N,同时,P每向前移动一步,Q就向前以东两步,已知环的周长是L,问P,Q两点相遇在哪点上?如下图所示:P点是环的入口点
假设P,Q两点相遇时,P点移动的距离是X,则有以下等式:
X-N = 2*X - L;
=>X= L-N
那么我可以从上图看到相遇点离入口点的距离为:L-(L-N)=N
综上所述:
假设单链表的总长度为L,头结点到环入口的距离为a,环入口到快慢指针相遇的结点距离为x,环的长度为r,慢指针总共走了s步,则快指针走了2s步。另外,快指针要追上慢指针的话快指针至少要在环里面转了一圈多(假设转了n圈加x的距离),得到以下关系:
s = a + x
2s = a + nr + x
=>a + x = nr
=>a = nr - x
由上式可知:若在头结点和相遇结点分别设一指针,同步(单步)前进,则最后一定相遇在环入口结点
通过上面的证明题发现数学知识在编程世界中真的很重要呀~~
总结:我们看到这里面有一个核心的地方就是第一个问题,判断有没有环的情况,采用了两个指针:快指针和慢指针,这个在处理一些链表的问题中尤其重要,比如下面的两道关于链表的题目:
第一题:已知单链表的头指针,查找到倒数第K个节点
这道题的通俗的解法就是先遍历一边链表,得到链表的长度N,然后再从头开始遍历N-K个节点即可
但是现在如果要求只遍历一遍链表的话,该怎么操作呢?
这时候就可以借助快指针和慢指针了
我们定义一个快指针P和慢指针Q,先让P指针走到K个节点位置,然后Q指针从头指针开始和P一起移动,当P移动到尾部的时候,那么此时Q节点所在的位置就是倒数第K个节点。
第二题:已知单链表的头结点,查找到链表的中间节点
这道题的通俗的解法和上面的方法一样,就是先遍历一边链表,得到链表的长度N,然后再次遍历N/2个节点即可
但是现在同样的如果要求之遍历一边链表的话,该怎么操作呢?
这时候我们同样可以借助快指针和慢指针了
我们定义一个快指针P和慢指针Q,P和Q同时从头指针出发,快指针P每次移动两步,慢指针每次移动一步,当快指针P到尾部的时候,慢指针Q所在的位置就是中间节点的位置。
通过上面的两道题目我们可以看到快慢指针的在解决单链表的相关问题上还是很有用的~~
下面在来看一下还有一个技巧就是在解决第二道题目的时候,那个求环的入口节点,这个当时真的是没有任何头绪,所以这时候就要求我们又很好的数学功底了,能够发现相关的规律,然后总结出定理,这样就可以将问题简化了。
分享到:
相关推荐
126邮箱页 html源码 单页源码 网站后台登陆界面HTML源码
武汉开放数据创新大赛——烽火杯文件
mmexport1713881481676.png
Digital currency trading platform landing pageAdobeXD源码下载设计素材UI设计
了解Java及环境搭建
专业实习-三创赛
第三届全国大学生服务外包创新创业大赛(智能楼宇能耗管理系统)
allPort Design SystemAdobeXD源码下载设计素材UI设计
系统介绍 本系统根据企业的需求进行设计,具有以下特点:界面友好,采用人机对话方式,操作简单。信息查询灵活、快捷、数据存储安全。实现用户管理功能,主要包括用户登录与注册功能。对用户输入的数据,系统进行严格的数据检查,尽可能排除人为错误。要实现模糊查询功能,允许用户查询一类的文章。系统运行稳定,安全可靠。 操作注意事项 本系统的后台用户名为:mr,密码为:mrsoft 操作流程 (1)通过首页提供的数据可实现搜索数据。 (2)可通过首页的“进入论坛”超链接进入论坛区,此时用户可以浏览文章,并为文章添加评论。 (3)访客可登录系统来发表文章。
【资源说明】 【备注】 1、该项目是高分毕业设计项目源码,已获导师指导认可通过,答辩评审分达到95分 2、该资源内项目代码都经过mac/window10/11/linux测试运行成功,功能ok的情况下才上传的,请放心下载使用! 3、本项目适合计算机相关专业(如软件工程、计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载使用,也可作为毕业设计、课程设计、作业、项目初期立项演示等,当然也适合小白学习进阶。 4、如果基础还行,可以在此代码基础上进行修改,以实现其他功能,也可直接用于毕设、课设、作业等。 欢迎下载,沟通交流,互相学习,共同进步!
hikvision-find-info.yaml
Portfolio_Responsive_Landing_PageAdobeXD源码下载设计素材UI设计
【资源说明】 高分毕业设计 基于Python+Flas+微信小程序的教室空间可视化分析系统源码+部署文档+全部数据资料高分毕业设计 基于Python+Flas+微信小程序的教室空间可视化分析系统源码+部署文档+全部数据资料 【备注】 1、该项目是高分毕业设计项目源码,已获导师指导认可通过,答辩评审分达到95分 2、该资源内项目代码都经过mac/window10/11/linux测试运行成功,功能ok的情况下才上传的,请放心下载使用! 3、本项目适合计算机相关专业(如软件工程、计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载使用,也可作为毕业设计、课程设计、作业、项目初期立项演示等,当然也适合小白学习进阶。 4、如果基础还行,可以在此代码基础上进行修改,以实现其他功能,也可直接用于毕设、课设、作业等。 欢迎下载,沟通交流,互相学习,共同进步!
Bakery_Responsive_Landing_PageAdobeXD源码下载设计素材UI设计
Crypto_Responsive_Landing_PageAdobeXD源码下载设计素材UI设计
code-aipaca
DailyRecipeAdobeXD源码下载设计素材UI设计
数据手册
算法 堆排序12.java 使用java代码实现 堆排序12.java 使用java代码实现 堆排序12.java 使用java代码实现 堆排序12.java 使用java代码实现 堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.jav
微信小程序