题解 | #链表中环的入口结点#

算法分析：

现在将快慢指针在同时定在链头，并且快慢指针速度不同，快指针每次移动2，慢指针每次移动1

$v_1=2,v_2=1v\_1\; =\; 2,v\_2\; =\; 1$

$s_1,s_{2}s\_1,s\_2$分别代表链表不循环的元素个数和循环元素的个数。

当慢指针到达环入口时，记快指针已经从环头开始走的距离为$d_{1}d\_1$：

1. 假设 ，此时快指针位置距入口$s_{1}s\_1$,慢指针刚好在入口 第一次相遇时，设距离入口为d

​ 分析：慢指正还要走多少步才能重新到达入口呢？s_2-d = s_1\ ​ 所以，现在，慢指针在距离入口为d的位置，快指针重新回到开始位置，快指针慢下来 $v_1=1v\_1\; =\; 1$ ​ 当慢指针重新到达入口的时间t：

​ 这个时间刚好快慢指针同时到达入口 ，此时函数返回开（或者慢）的位置

2. 如果 $s_1>n{s}_{2}s\_1>ns\_2$,这里n是使得上不等式成立的最大整数.(如此) 此时快指针距离入口$s_1-n{s}_{2}s\_1-ns\_2$，慢指针刚好在入口 第一次相遇时，设慢指针走的距离为d

​ 分析第一次相遇时，慢指针距离入口有多远的距离呢？\ ​ 分析： ​ 所以可见，d就是快慢指针到入口的距离。 ​ 再分析，慢指针再走距离$s_{1}s\_1$,可以到达入口吗？$d+s1=(n+1)s_{2}d+s1\; =\; (n+1)s\_2$ ​ 显而易见，慢指针又重新到达入口。 ​ 如果快指针重新回到开口，并且速度变为每次只走一步(与慢指针速度相同)，那么，快慢指针同时在入口相遇。 ​ 此时返回快（或者慢）指针，就可以啦！