快慢指针在链表中的一些证明
目录
一、一定会相遇的证明
二、环长度
三、连接点
四、带环链表总长度
五、例题
一、一定会相遇的证明
证明1
1、如果链表没有环，那么快指针比慢指针先到达尾部（null)。
2、如果链表有环的话，因为快指针走的比慢指针快，所以在环中相遇的过程可以看作是快指针从环后边追赶慢指针的过程。
用递归法证明，快慢指针一定会相遇：
（1)快指针与慢指针之间差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。 （2)快指针与慢指针之间差两步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况。 （3)快指针与慢指针之间差N步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差(N+1-2)即N-1步。重复这个过程，直到快指针和慢指针相遇。
因此，此题得证。所以快指针必然与慢指针相遇。
证明2
如果链表存在环，快慢指针就一定能相遇。设快指针每次移动q步，慢指针每次移动s步，环的长度为n，环之前的链表长度为m，如下图所示
假设慢指针第一次到达环时移动了x次，位置为a，此时快指针也移动了x次，位置为b，
则此时快慢指针相遇的等式为
，
也即
（1）成立，
又：
（2），
（3），
由（1）（2）（3）可得出
成立，显而易见（q(x+y)-s(x+y) == n *k(k=1,2,3,…)），x+y是n的整数倍的时候，该式一定成立。
————————————————找环的起点分割线——————————————
假设快指针每次移动2步，慢指针每次移动1步，则根据上述证明可知，
，
，相遇的位置在y处；求环的起点，就是求m的大小，此时令一指针p1从头结点出发，每次移动1步，令一指针q1从相遇处出发，每次移动1步，则p1与q1再次相遇的地方就是环的起点处，因为此时两个指针均移动m步，由
可知，相遇
推导：慢指针进入环后，快指针最多多绕一个圈。
快指针F先进环，慢指针S后进。
假设慢指针进环那一刻快指针差m步能追上（0<= m < Length环），根据上边结论，两个指针走m次就会相遇了。
因为m < Length环，所以快指针在慢指针进环那一刻最多比慢指针多绕一个圈。
二、环长度
快指针和慢指针第一次相遇时的节点pq（碰撞点），快指针和慢指针从该点开始继续往前走，再次碰撞时所用的操作数就是环的长度Length环。
证明:由上边的推导可得，这里的m为Lengh环。
三、连接点
假设慢指针进入环中时，即连接点p，快指针（q）需要m步才能追上慢指针。
p和q第一次相遇时，碰撞点在pq处。此时，p走到pq时用了m步。
假设head到p的距离为a，环长度为Length环，慢指针走了s步，则快指针走了2s步。
从上图可知:
s = a + m
2s = a + m + n * Length环（n为快指针绕环的圈数）
可得
a = n * Length环 - m
也就是：若在头结点和相遇结点分别设一指针，同步(单步)前进，则最后一定相遇在环入口结点p。
可根据这个结论来找到入口节点。
四、带环链表总长度
找到连接点p后，求head到p的长度，再加上环的长度，即为链表的总长。