142.环形链表相关结论数学性证明。_环形链表 思路数学论证

环形链表

上面是题目链接，首先我们就画一个图来说吧

我们链表起点到环起点为x，环起点到两快慢指针相遇的点的距离为y，两快慢指针相遇的点的距离到环起点的距离为z。也就是说环一周的长度为y+z，即为s。

ps:我这里所有的距离，指的是前结点指向后结点的顺时针方向的距离

 

这题其实解题思路网上有很多，但大多数的只给思路和结论用，不给证明。比如：

①设置一个慢指针，一个快指针，若有环路快慢指针必会相遇。这个不需多言，由于快指针比慢指针每次多走一步。存在环的话，必定相遇。

②这两指针在环中第一次相遇的时候，慢指针一定只走了一次x+y,而不会多走一圈，即x+y+n(y+z)。正常人比如我，看到这结论就蒙圈呢？为什么呢？

③将快指针重新移动到链表开头，并让快慢指针每次都前进一步。当快慢指针第二次相遇时，相遇的节点即为环路的开始点。看到这，我又不懂，这是为啥？

所以今天我的重点不是说明这题怎么做，而是尽量去证明②和③，这里称慢指针为slow，块指针为fast

首先关于②

1）fast一定比slow先进环，说明，当slow在环的起点时，fast一定在环的某个位置。

2）我们设此时fast和slow的距离为m，首先m<s，不可能比环长度还大。

3）由于每次fast都比slow都快一步，就是说只需要m步，fast必可以追到slow，而slow走完整个环需要s步，所以必定会在slow的第一次环内fast就追上slow，即该两点相遇。

然后关于③

1）到两点第一次相遇时，slow走的距离为x+y,fast走的距离时x+y+ns，其中n代表圈数，n>=1。

2）由于fast的速度是slow的两倍，所以有(x+y)*2=x+y+ns，两边消去x+y,则x+y=ns。由于s=y+z,所以x+y=n(y+z)==>x=(n-1)(y+z)+z==>x=(n-1)s+z。

3）这里我们思考推导式左边x代表链表起点到环起点的距离，z为第一次相遇点到环起点的距离，前者比后者长了个(n-1)s,而s又是环的长度。

4）不妨看看一般情况，若n=1，则x=z，那么如果有两个点，一个从起点出发，一个从第一次相遇点出发，都保持一次一步的速度，最后会在环起点相遇。n=2的时候同理，只是从第一次相遇点出发的点会多走环一圈，再在环起点相遇。

5）也就是说此时，我把fast指针移回链表起点，速度变为和slow一样的一次一步，那么slow和fast再次相遇的结点必然是环起点，只是n的不同会影响从第一次相遇点出发的slow结点多走的环路圈数。

 

自此，证毕