关于带环链表的结论

简介: 关于带环链表的结论

先来个图~

上结论,一个指针从链表的起始点出发,另一个指针从链表的相遇点出发,二者会在入环点相遇。

浅浅滴解释一下入换点与相遇点

入环点:指针开始进环后的第一个点

(2为入环点)

相遇点:slow指针与fast指针相遇(fast指针追上slow指针)的点

开始证明!

先介绍一下这个结论的背景,这里有一个slow指针,每次移动一步(slow=slow->next),还有一个fast指针,每次移动两步(fast=fast->next->next),fast指针会在环里面追上(相遇)slow指针。

证明:

注意:slow,fast进环后是按顺时针方向运动,相不相遇主要看的是二者间相对距离减少几,

例如slow每次走一步,fast每次走三步,那么它们每走一次相对距离减少二

距离:N N-2 N-4 N-6 二者是否相遇取决于N是奇数还是偶数,奇不遇偶遇

现在开始证明标题提到的结论

相关文章
|
8月前
|
机器学习/深度学习 编译器 测试技术
带环链表 复杂链表 刷题+心得【C语言实现 】
带环链表 复杂链表 刷题+心得【C语言实现 】
32 0
|
3天前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
11月前
|
索引
【LeetCode】环形链表II+结论证明
【LeetCode】环形链表II+结论证明
52 0
|
11月前
|
索引
【LeetCode】环形链表+结论证明
【LeetCode】环形链表+结论证明
45 0
|
C语言
C语言:带你轻松干掉 腾讯笔试大题 带环链表
C语言:带你轻松干掉 腾讯笔试大题 带环链表
66 0
链表带环问题
链表带环问题
87 0
数据结构练级之路【链表带环问题】
数据结构练级之路【链表带环问题】
【数据结构】研究链表带环问题
我们只要判断它们是否相遇了,就能确定是否带环,因为如果没有带环的话,那就不可能相遇,快指针肯定先走出去。
99 0
|
Java 索引
(Java)链表OJ题(环形链表,判断链表是否带环,求入环的第一个节点)
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
(Java)链表OJ题(环形链表,判断链表是否带环,求入环的第一个节点)