一 目的
- 定理推论证明
二 定理推论证明
image.png
上述变量名称解释
P1：链表的起点
D：链表的环入口（假设链表有环）
P2：快慢指针相遇的位置
X：链表起点 P1 到环入口 D 的距离
Y：链表环入口 D 到相遇节点 P2 的距离
Z：快慢指针相遇点 P2 到环入口 D的距离
C：链表环的距离，即 y + z
开始证明
假设快慢指针相遇时，快指针在环内走了m圈，慢指针在环内走了n圈，则有如下公式
- 快指针总共走的距离为
x + y + m * c
- 慢指针总共走的距离为
x + y + n * c
假设快指针每次走2步，慢指针每次走1步，则快指针走过的距离是慢指针走过距离的2倍
(x + y + m * c) = 2(x + y + n * c) 结论1
又因为环长为c = z + y，所以得出下面结论
(x + y + m * c) = 2(x + y + n * c)
-> c(m - 2n) = x + y
-> c(m - 2n) = x + c - z
-> x = mc - 2nc - c + z
-> x = (m - 2n - 1) * c + z 结论2
image.png
入上图所知，
- 假设 一个指针
point1从起点出发，走了(m-2n-1)*c步到达了P1位置。 - 另外一个指针
point2从相遇点P2开始出发，也走了(m-2n-1)*c步，最终还是停留在P1的位置（相当于绕环走了c圈而已）。 - 这个时候，第一个指针
point1距离环入口的距离是z（由结论2得知），第二个指针point2距离环入口距离是z（之前的假设），所以两个指针再同时走z步，就会在环入口D处相遇
结论
要想知道环入口位置，只需先使用快慢指针，在环内找到相遇点P2，然后再让两个指针，一个从起点开始出发，一个从相遇点P2开始出发，每次走一步，最终相遇的地方，即为环入口D，走过的距离，也就是环入口的距离X，定理推论完毕。
