快慢指针判断链表中是否存在环查找环的起始位置

2024-02-27 09:38

本文主要是介绍快慢指针判断链表中是否存在环查找环的起始位置,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

判断链表中是否有环?
   使用快慢指针, 慢指针一次走一步, 快指针一次走两步, 当快慢指针相遇时,说明链表存在环
为什么快指针每次走两步而慢指针每次走一步呢?
   因为slow指针和fast指针都会进入环内, 就像在环形跑道内不同位置的两个人;slow指针在后面,
fast指针在前面, 但实际上fast指针也在追slow指针, 希望能在环内超slow指针一圈(当超过一圈时会
相遇)。那么fast指针总会追上slow指针的;

那么fast指针会不会跳过slow指针呢(为什么快慢指针的步骤差必须为1呢)?
   不会的, 因为fast每次走2步,slow每次走1步,假设两者在环内的距离差为N, 那么每次走动, 距离差N都
会缩小一步, 因为fast与slow指针的步长差是1(1也是fast与slow指针之间距离的最小单位);最终,N会减少到0,
也就是两者会相遇。如果fast指针每次走两步,那么当fast与slow间只剩一步时, fast指针会错过slow指针;

如何查找链表环的起始位置?

 

                 

 

假设slow指针和fast指针从A点出发, 最终在C点相遇, 那么可以判断链表中存在环; 此时slow指针移动距离为L1+L2, fast指针移动距离为: L1+L2 + L3+L2; 

由于fast指针速度是slow指针的2倍, 那么如果slow指针移动的距离为S, 那fast指针移动的记录就是2S, 所以 2 * (L1+L2) = L1+L2+L3+L2, 因此可以得出: L1 == L3

那么如果将fast指针置于C点, slow指针置于A点, 这次以相同的速度移动, 当两个指针再次相遇时, 就是环的起始位置B点

              

  • 伪代码:

fast = head
slow = head //快慢指针都指向头部
do {快指针向后两步慢指针向后一步
} while 快慢指针不相等时
if 指针都为空时{return null // 没有环
}
while 快慢指针不相等时{快指针向后一步慢指针向后一步
}
return fast

 

这篇关于快慢指针判断链表中是否存在环查找环的起始位置的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/751979

相关文章

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

POJ1269 判断2条直线的位置关系

题目大意:给两个点能够确定一条直线,题目给出两条直线(由4个点确定),要求判断出这两条直线的关系:平行,同线,相交。如果相交还要求出交点坐标。 解题思路: 先判断两条直线p1p2, q1q2是否共线, 如果不是,再判断 直线 是否平行, 如果还不是, 则两直线相交。  判断共线:  p1p2q1 共线 且 p1p2q2 共线 ,共线用叉乘为 0  来判断,  判断 平行:  p1p

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

easyui同时验证账户格式和ajax是否存在

accountName: {validator: function (value, param) {if (!/^[a-zA-Z][a-zA-Z0-9_]{3,15}$/i.test(value)) {$.fn.validatebox.defaults.rules.accountName.message = '账户名称不合法(字母开头,允许4-16字节,允许字母数字下划线)';return fal