[寻找环链表入口点] 快慢指针数学原理剖析_为什么链表环形入口可以用快慢指针找到

链表环路检测及环入口定位是一个非常经典的算法问题，它可在死锁检测等实际应用场景发挥重要作用。想必大家都知道这个问题应该使用快慢指针去求解，因为它具有最优的时间复杂度O(n)。但是大家可能对快慢指针的数学原理不是很清楚，为啥它能达到最优。详细读了这篇文章，大家必定豁然开朗，掌握快慢指针背后的数学原理。

 我们直接来看图。

先讲一下链表环路检测的原理，相比环入口定位，原理比较简单。

起点设置两个快慢指针，同时开始往后跑，每跑一次必须检测快指针是否到达链表末尾(下一个节点值为null)，如果到达链表末尾则证明该链表无环。如果该链表存在环，则快慢指针总有邂逅（相遇）的那一刻，由此每跑一次，除了检测快指针是否到达链表末尾，还需检测快慢指针所在节点是否相同，相同则代表两指针相遇了，即环存在。为什么环存在时快慢指针一定会相遇呢，想必不用过多解释了，举个简单生活中例子，两个人在足球场跑步，同一起点出发，跑的快的人一定会在某一时刻追上跑的慢的人（多跑一圈）。

现在来分析环入口定位的原理。

环入口定位的前提是先找到快慢指针相遇点，即上述所讲的链表环检测操作（注意存在一个限定条件，快指针的步长必须为2，慢指针步长必须为1）。当找到相遇点后，在起点处和相遇点处分别设置指针p1和p2，步长均为1，它们同时往后跑，当p1，p2相遇时，它们的相遇点便是环入口。

现在来一波数学推理，证明一下上述算法的正确性。

x为起点至环入口点的距离，y为环入口至快慢指针相遇点的距离，z为快慢指针相遇点至环入口的距离。

假设相遇时，快指针绕环跑了m圈，则快指针所跑路程为；慢指针绕环跑了n圈，则慢指针所跑路程为。因为快指针速度为慢指针两倍，则相遇时快指针所跑路程亦为慢指针两倍，即。

等式推导如下：

（由图得知）

由推导结果可知，起点至环入口的距离x为环周长c的倍再加快慢指针相遇点至环入口点的距离z。

在起点处和快慢指针相遇点处分别设置指针p1，p2，两指针速度一致，当p1走了$(m-2n-1)*c$的距离时，p1所处位置距离环入口点的距离为z。此时，p2同样走了跟p1一样的距离$(m-2n-1)*c$，即绕着环走了圈。

我们知道p2的出发点正好是快慢指针的相遇点，即便绕着环走了圈后，p2所处位置还是在快慢指针相遇点。因此，p2和环入口点的距离为z。

从上述推算，我们已经得知p1和p2距离环入口点的距离相同，均为z。

两个指针再往后走z的距离，便会相遇，相遇点便恰好是环入口点。

至此，环入口定位的算法原理讲解完毕。

现在来分析一波边界情况，以此证明上述公司的正确性。慢指针最少需要跑0圈，即进入环后第一次经过相遇点就被快指针追上了，所以n最小值为0。快指针要追上慢指针，至少要比慢指针多跑一圈，根据这些已知条件，可作推理如下：

已知 

已知 

得 ，即

将 带入等式 

得，即

因此，证明出x不可能为负，即起点距离环入口点距离不为负，符合常规事实，算法严谨性得证。

希望看完这篇文章的读者朋友们能够恍然大悟，掌握链表环问题的核心原理。如有不懂的地方，欢迎评论区留言。