当前位置 : 主页 > 编程语言 > c语言 >

带环的单链表追击之拓展证明

来源:互联网 收集:自由互联 发布时间:2023-09-07
对于单链表有环问题,上一期,我们已经详细讲解了!!而快慢指针功不可没!! 对于本期 我们再次回顾,链表有环问题时,不难心中存在一个疑问,一定能追得上吗? 会不会错过?

对于单链表有环问题,上一期,我们已经详细讲解了!!而快慢指针功不可没!!

对于本期 我们再次回顾,链表有环问题时,不难心中存在一个疑问,一定能追得上吗? 会不会错过??

那么为什么??为何能追上,什么情况下会追不上!!就是我们今天讨论的重点!!


假设单链表有环,快指针每次走两步,而慢指针每次走一步!!那么,快慢指针总会全都入环,并且一定是快指针先入环。当慢指针入环的时候,两个指针相差的距离,最坏的情况是环的长度 - 1

而每次,快指针总是比慢指针多走一步!!这样会之间的距离就会缩小一步!!并且不会出现套圈的现象!!而且在慢指针走完一圈之内快指针一定会同慢指针相遇

由于方便理解与论述,请看下面的图示 :>

带环的单链表追击之拓展证明_证明环内相遇

以上仅仅是一种情况,那么问题又来了!!如果,每一次 slow 走一步,而 fast 会走 X (X >= 3) 步呢??

会相遇吗?又是否会错过??

还是同样,为方便理解以及更加形象化,请看下面的图解 :>

带环的单链表追击之拓展证明_带环单链表_02

由以上过程的讨论,我们不难看出,对于 N 的奇偶性需额外注意的!!

另外步数相差 偶数倍 与 还是相差 奇数倍 也还是有区分的!!

下面,我们再证明一道  ::>

让一个指针从链表的起始位置开始遍历链表,同时让一个指针从判环时相遇的位置开始绕环运行,两个指针都是每次均走一步,最终会在第一次入环的位置相遇。请证明!

本道证明题,是不是特别有熟悉感! 其实,它是上一期最后一道题的拓展!!


原题如下 ::>

给定一个链表的头结点 head,返回链表开始入环的第一个结点。如果链表无环则返回 NULL。

而代码实现则如下 :>

带环的单链表追击之拓展证明_拓展_03


为了更加容易理解证明过程,还是图像形象化比较好,如下所示 :>

带环的单链表追击之拓展证明_证明环内相遇_04


如图所示,假设,H为起始点,E为入环点,

M为相遇点,也是 fast开始追击 slow 的起始点(或者说,slow 刚刚入环的时候,fast 所在的位置)

设 长度ME 为 L ,EM之间的距离为X , ME 间距为 C - X

判环过程中,快指针与慢指针相遇时,有 ::>

slow = L + X

fast = L + X + nC ,(n ,1, 2, 3, 4, 5, 6 ···)

现请注意 :>

1.慢指针入环时,快指针已经在环中运动了n圈。n 至少为 1

因为 :slow 入环时, fast 位于 M 点处,之后追击 slow 又在M点处两者相遇

2.slow 入环,fast 会在slow 完成一圈之内,追上 slow

因为:fast 与 slow 之间的最大距离为环的长度 C, 由于fast 比 slow 要快走一步,每一次会使得之间的距离缩短一个单位,因此 slow 入环之后,fast 在一圈之内一定会追上 slow

由于满足 fast 的行进速度是slow的两倍(噢!!这让我想起了高中物理的速度是矢量,是有方向的,前面的表述口误了,哈哈

上一篇:C++,OpenCV安装与配置(1)
下一篇:没有了
网友评论