整理部分双指针算法（重点：龟兔算法，含证明）

一、同速指针

问题：从单链表中找到倒数第n个结点。

直觉算法

遍历一遍链表，得到链表长度 length，然后指针重新指向表头，设置从 0 开始的计数器，指针每往后移动一个，计数器加 1 ，当计数器变为 length - n 时，就找到了倒数第 n 个结点。

双指针算法

使用两个指针，假设为 p、q，p 指向表头，q 先向后移动指向第 n 个结点。然后两个指针同时向后移动，直至 q 走到链表末尾。此时 p 就指向了倒数第 n 个结点。

二、快慢指针

问题一：查找单链表的二分位点

直觉算法

遍历链表获得链表长度，然后再计数获得中间结点。

快慢指针算法

使用两个指针，假设为 slow、fast，两者初始时都指向表头。slow 一次向前移动一个结点，fast 一次向前移动两个结点。当 fast 移动到链表末尾，slow 就指向了链表的中间结点。

问题二：判圈：如何检测一个单链表是否有环？如果有环，如何确定环的起点以及长度？

直觉算法

用哈希表保存已经走过的结点指针，查找判断当前指针是否在之前已经出现过。

龟兔算法（Floyd cycle detection）

龟兔其实是快慢指针，假设为 slow、fast，初始时都指向单链表表头，slow 指针每次移动一个结点，fast 指针每次移动两个结点。如果 slow、fast 相遇，则说明有环。如果 fast 走到链表末尾还没与 slow 相遇，则无环。

floyd.png

符号约定及定义： 约定单链表表头为 A，环起点为 B，龟兔相遇结点为 C。定义 |AB| 表示沿单链表方向结点 A 到结点 B 的距离，距离值的定义为乌龟走的步数，如图 |AB| = 3。环长为 L，表示乌龟从环起点出发回到环起点所走的步数。
令则从出发到相遇，乌龟所走的距离为:后面有证明乌龟不可能绕环超过一圈。
兔子所走的距离为：上面两式相减，并联立乌龟所走的距离得：由此可知，m+n是环长L的整数倍。

环起点： 当龟兔相遇后，令乌龟返回表头 A，兔子留在相遇结点 C，两者都一次向前移动一个结点（此时已是同速指针），此时乌龟往环的位置赶，兔子在环内转圈圈。当乌龟赶到环起点时，兔子也移动了 m，加上初始时距环起点的 n，兔子距环起点 m+n，为环长 L 的整数倍，此时兔子也刚好到达环起点，两者再次相遇，相遇结点就为环起点 B 。

环长度： 接着上一步，龟兔同时指向环起点，此时让两者中的一个留在 B，一个逐结点向前推进，并同步计数，当两者再次相遇就得到了环长 L。

证明快指针 fast 一定会追上慢指针 slow。

slow 在 fast 前一个结点时，两者经过一次移动两者相遇。
假设 slow 在 fast 前 k 个结点时，经过有限次移动两者一定会相遇。
则当 slow 在 fast 前 k+1 个结点时，经过一次移动，变为 slow 在 fast 前 k 个结点，则经过有限次移动两者一定会相遇。
得证。

证明慢指针 slow 绕环不可能超过一圈。

单链表本身为环的情况
slow、fast 同时从环起点（表头）出发，当 slow 绕环一圈时，由于 $D_{fast}=2D_{slow}$ ，fast 刚好绕环两圈，此时两者在环起点相遇。
下面证明此前不可能相遇（出发时不算），即 slow 绕环一圈时是第一次相遇：
假设 slow、fast 在此之前相遇，相遇结点和环起点的距离为 $n(0<n<L)$ ，则 $D_{slow}=n$ $D_{fast}=n+L$ 即 $n+L=2n\Rightarrow n=L$ 与假设矛盾，故假设不成立。
单链表有环，但不全为环的情况
考虑 fast 追上 slow 要走的最远距离是，fast 刚好在 slow 的前一个结点。
首先证明这种极端情况不可能发生在 slow 的上一步已经在环内时：
假设 slow 的上一步已经在环内，且在 slow 的当前步出现了上述极端情况。
回退到上一步可以发现，slow、fast 已经相遇，算法结束。故假设不成立
所以这种情况只能发生在 slow 刚进入环起点时，fast 在 slow 的前一个结点。
此时相遇之前两者之间的距离小于情况一，所以在 slow 绕环一圈之前，两者就已经相遇。