快慢指针判断链表是否有环，找到环的入口，公式推导；_指针判环

题目：给定一个循环链表，实现一个算法返回这个环的开始结点。
定义：循环链表就是链表中一个结点的指针指向先前出现的结点，导致链表中出现环。
（补充：快指针每次移动两步，慢指针每次移动一步）
例子：
输入：A->B->C->D->E->F->G->D （假设在E点相遇）
输出：C

思路，设置如上图所示的变量（图是网上找的）

1. K： 没入环之前两个指针走过的距离（注意，是距离，不是结点个数）
2. X：相遇点处，逆向到入环点的距离
3. Y：相遇点处，顺时到入环点的距离
4. N：相遇时，快指针完整绕环的圈数
5. n： 相遇时，慢指针完整绕环的圈数

公式推导：
慢指针走过的路程：K + X + n*(X+Y)
快指针走过的路程：K + X + N*(X+Y)

两者是二倍的关系 -》2* ( K+X+n(X+Y) ) = K+X+N(X+Y)
得到：K + X = (N-2n) * (X + Y)
若此方程成立 则 此方程有解（即能够相遇）
（忘了数学上怎么证这个式子了，最后证明完就是：不论K是否为0，此方程有解）

结论一：快慢指针能够判断是否有环

也就是说能够相遇就代表有环

继续分析这个公式得到的结果K + X = (N-2n) * (X + Y)
含义为：K+X的值恰好为圈数的整数倍；
即K + X = A* （X+Y）
也就是 K+X 大于等于 1圈的距离，且为整数倍；
若将相遇处的快指针移动到起点处，两指针以相同每次1步的速度前进，当快指针走K，慢指针走 圈数的整数倍 - X
—》两者会在入口处相遇

结论二： 将快指针移至起点，与慢指针同速行进，两者会在环入口处相遇；

代码实现在后面这篇中：
环形链表I II，判断链表是否有环（代码实现）