环链表找入口原理证明

一 目的

• 定理推论证明

二 定理推论证明

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

入上图所知，

1. 假设 一个指针point1从起点出发，走了(m-2n-1)*c步到达了P1位置。
2. 另外一个指针point2从相遇点P2开始出发，也走了(m-2n-1)*c步，最终还是停留在P1的位置（相当于绕环走了c圈而已）。
3. 这个时候，第一个指针point1距离环入口的距离是z（由结论2得知），第二个指针point2距离环入口距离是z（之前的假设），所以两个指针再同时走z步，就会在环入口D处相遇

结论

要想知道环入口位置，只需先使用快慢指针，在环内找到相遇点P2，然后再让两个指针，一个从起点开始出发，一个从相遇点P2开始出发，每次走一步，最终相遇的地方，即为环入口D，走过的距离，也就是环入口的距离X，定理推论完毕。