一、判断链表中是否存在环的方法及证明

首先说明一点就是如果链中存在环，可能整个链是一个环，也可能是该链表的后面一部分形成了环。如何判断链表中是否存在环，经典的判断方法就是利用两个指向链表头节点的指针，同时移动，两个指针每次移动的节点数是不一样的，如果存在环，那么这两个指针随着移动次数的增加，肯定会某个节点相遇，否则移动快的指针会到率先达链表末尾，即不存在环。

有没有同学会疑惑：如果存在环，这两个移动速度不同的指针一定会相遇吗，两个指针速度值设置为多少合适呢？下面我们来证明一下：如果存在环，不管这两个指针的移动速度为何，同时移动若干次后，这两个移动速度不同的指针肯定会相遇。证明过程如下：

（1）设两个指针为P1、P2，P1的移动速度为每次移动m个节点，P2的移动速度为每次移动n个节点，0 < m < n。P1和P2初始都指向链表头节点。另设链表中环中的节点为L1(L1 >= 2)，链表剩余节点个数为L2（L2 >= 0）。

（2）我们利用假设法来证明，即假设会相遇，那么接下来我们要做的就是能否来找到一个次数K，这个K使下面两个条件a和b同时成立

a：(L2 + n*K) – (L2 + m*K) = h*L1 => K * (n – m) = h * L1 => K*(n-m)/L1为不小于1的整数，h为整数，代表P2节点比P1节点在环中多走的圈数。如果相遇了，那么P2节点肯定比P1节点在环中都走了若干圈，所以推出这个等式成立；如果这个等式成立，也能表示P1和P2肯定能同时走到同一个节点上。

b：m*K >= L2 => K >= L2/m,这个条件之所以存在，是因为P1和P2肯定是在环内相遇，环外由于速度不同，是不可能相遇的，那么P1肯定进入环内了,那么环外的节点肯定都经历了。

（3）在m、n、L2、L1给定的条件下，不管这四个变量的值为多少，我们都能找到符合a和b的一个最小整数，就是我们要找的次数K。比如m = 2，n= 3，L1 = 4，L2 = 3，我们要找的K满足的条件是K/4为不小于1的整数，并且K >= 1.5，可得满足条件的最小整数为4，即同时移动4次，P1和P2会相遇。为了便于理解，我们以此为例，画图说明一下移动过程，如下图所示：

综上可知：如果链表中存在环，那么两个指针初始指向位置均为头节点，并且两个指针移动速度只要不同并且均大于0，那么同时移动若干次后，这两个指针肯定能够相遇。如果这样两个指针能够相遇，也说明链表中肯定存在环。

二、问题升华：如果链表中存在环，那么如何定位到链表中形成环的头节点呢？

该问题的算法是基于问题一的，但是对两指针的移动速度有了一个限制，就是两指针速度最好相差1，即n-m=1，两个指针相遇之后，我们只需把P1初始化为头节点，P2的位置保持不变，然后两指针同时移动切每次均移动一个节点，那么这两个指针会再次相遇并且相遇时所处的节点就是环的头节点。

证明过程：我们设两节点相遇的时候，P1节点在环内所走的圈数是q1，P2节点在环内所走的圈数是q2，再设相遇所处的节点位置离环的头节点的距离为d，那么可得到下面两个等式：

m*K = L2 + q1*L1 + d;

n*K = L2 + q2*L1 +d;

推导出n*(L2 + q1*L1 + d) = m*(L2 + q2*L1 +d) => d = (m*q2-n*q1)/(n-m)*L1 – L2，看到这个等式，我们设想，如果(m*q2-n*q1)/(n-m)为整数，那么如果P2再走L2步，刚好可以走到环的头节点，而把P1初始化为链表的头节点，那么P1走L2步，也能刚好走到环的头节点。如何能让(m*q2-n*q1)/(n-m)为整数呢，那就是让n-m=1。

所以可得结论，如果想找到链表中环的头节点，则使用两个移动速度相差1的指针，先让它们相遇，然后在相遇的节点处，一个指针保持不变，另一个指针初始化为链表的头节点，继续让他们同时移动，并且每次移动一个节点，那么它们定会在环的头节点相遇。

闲来无事，对上述两个问题的解法加以证明，也好做到用起来心中无疑虑。