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

>>>>>>>>>>>>>>>我使用了同余!!!点此了解解题思路及数学原理!<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

其他题解光讲原理不讲思路，知其然不知其所以然，这可不好。我来讲一讲解题的原理吧。
这道题的知识点其实是 $同余$ ，但是用的知识点比较浅，主要考察的是思路。

预备知识

简单说一下同余。同余的形式一般如下： $a \equiv b (mod \ d )$
它的意义其实很简单，熟悉编程的大家早就见过了，即： $a \ mod \ d == b \ mod \ d$ 。
带入这个题中，设d为环的长度，说白了就是我们只关心游标在环的哪个节点上，不关心它套了多少圈。
设圈长为d，显然这道题里同余都是以 $d$ 为底的(即 $blabla \equiv bla ( mod \ d)$ )，为了方便我后边就省略掉了。

解题思路

首先先判断有无环，使用经典快慢指针即可，反正出题人也没本事发明个新算法不是？
我们把具体情况画出来。其中， $O$ 是列表头， $A$ 是环入口, $B$ 是快慢指针交汇的地方， $OA$ 、 $AB$ 、 $BA$ 的长度分别为 $a$ 、 $b$ 、 $c$ 。
图片说明
然后诸位大可以开始拔头发考虑如何从已知的O、B点挪到A点。

推导

所以，我们能从快慢指针那里学到啥呢？

设慢指针的移动距离为 $x$ ，则由：1. 快指针速度是慢指针两倍、2. 慢指针最后落在了B点，可得：

$\left\{ \begin{array}{1} x-a\equiv 2x-a \Rightarrow x \equiv 0 \\ x-a\equiv b \end{array} \right.$
由 $x \equiv 0$ 及 $x-a\equiv b$ 可得 $a\equiv -b$ 。已知 $b+c=d$ ，所以 $a\equiv -b \equiv d-b \equiv c$ 。
既然 $a\equiv c$ ，那把 $O$ 盘到环上它就正好与 $B$ 点重合！我在示意图中以 $O'$ 表示。单从套圈的角度来看, $O$ 等效于 $O'$ 。

可能有同学看到 $a\equiv -b$ 就兴奋了！没错！ $a\equiv -b \Rightarrow b+a\equiv 0$ ，因此我们从 $B$ 出发走 $a$ 步就走到 $A$ 了！(或者说,由 $a\equiv c$ 可知，走 $a$ 等效于走 $c$ 步)

那么如何走 $a$ 步呢？ (边界条件：如果 $B$ 就是 $O$ ，那么就不用走了，直接返回 $O$ ，退出)
很简单， $a\equiv c$ 嘛！两个慢指针分别从 $O$ 、 $B$ 出发，相交处就是 $A$ 。

没反应过来？那这样看： $b+a\equiv b+c \equiv d \equiv 0 (mod \ d)$ 。 $0$ 不就代表着环的入口 $A$ 嘛，至于两个指针要转几个圈圈才能遇到，我不管～～～

以上。