单链表带环追击算法的拓展证明如何进行？

本文共计1092个文字，预计阅读时间需要5分钟。

针对单链表存在环的问题，我们已经详细讲解过了！指针功能不可没！而对于循环链表，我们再次回顾，链表存在环时，心中难免存疑，一定能追踪到吗？会不会错过？

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

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

那么为什么？？为何能追上，什么情况下会追不上！！这就是我们今天讨论的重点！！

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

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

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

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

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

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

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

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

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

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

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

原题如下 ::>

给定一个链表的头结点 head，返回链表开始入环的第一个结点。