快慢指针应用与证明

1. 概念

百度百科：

快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

步骤1: 快慢指针从链表头节点同时开始移动，快指针每次移动2格，慢指针每次移动1格，若快慢指针相遇则链表有环，否则链表无环。
步骤2: 有环情况下，快慢指针相遇时，慢指针位置不变，仍然每次移动1格，将快指针指回表头，同时改为每次移动1格。快慢指针同时开始移动，再次相遇处即为环的入口。

思考：如何利用快慢指针在有序链表中寻找中位数

为什么步骤1中快指针和慢指针一定会在有环链表中相遇？

思考如下情景：
情景1: 如果快指针与慢指针相差1格，继续走1步，则两指针相遇;
情景2: 如果快指针与慢指针相差2格，继续走1步，则两指针相差1格;
情景3: 如果快指针与慢指针相差3格，继续走1步，则两指针相差2格;
…
情景N: 如果快指针与慢指针相差N格，继续走1步，则两指针相差N-1格.

可根据数学归纳法推出，快指针和慢指针一定会在有环链表中相遇。
为什么经过步骤2可以找链表环的入口？

假设慢指针走了K格，快慢指针在M点相遇，从M点到起始点的距离也为K。

由于在步骤1快指针比慢指针走的快一倍，因此步骤1中慢指针走K格到达M，快指针走了2K格到达M. 因此在步骤2中，慢指针移动K次，仍然回到M点，而快指针指回表头，每次移动1格，移动K次也来到M点。因此快慢指针会在M点相遇。

由于步骤2中快慢指针每次都只移动1格，那么在链表环内，快慢指针会一直指向相同的节点，不存在分离与超越的情况，因此第一次相遇即是链表环的入口。