LeetCode：链表中是否存在环的证明问题。

Question

判断链表中是否存在环，通常使用双指针的方式，因为快指针、慢指针最终都会在环中相遇，但如何证明这两个指针一定会相遇呢，推倒过程如下：

我的疑问是：算式（3）是通过怎样的方式转换为算式（4）的呢？

------------------------分割线------------------------
反向证明如下：

Answer 1

我们的思路就是：设置两个快慢指针（快慢指针即两个指针起点相同，慢指针每次走一步，快指针走两步），让它们一直往下走，直到它们相等，说明有环。下面简单证明，

如上图，A 为链表第一个结点，B 为环与链表的交叉点，C 为快慢指针相遇的位置。假设环的长度为 r，则有

$$ frac {AB+BC+n_1r}{2}=AB+BC+n_2rag{左为快指针，右为慢指针} $$

其中，r 为正整数（即 1,2,3...），AB、BC 为非负整数（即 0,1,2,3...），n1 和 n2 分别为快指针、慢指针走的圈数，也为非负整数。接着化简为：

$$ AB+BC=(n_1-2n_2)r $$

一个有环的单链表，其 AB 和 r 是固定的，所以只要使 n1 和 n2 变化至使 BC 能满足是一个非负整数的条件即可。

仔细观察上式，我们发现，C 点一定是唯一的。

$$ BC=nr-AB ag{其中 $n=n_1-2n_2$} $$

这个证明很简单。对于任意两个满足条件的不同的 n 值，一小一大，相比较而言，它们计算出的两个 BC 值的差值一定是整除 r 的，所以 C 点必定唯一。

转自：https://ethsonliu.com/2019/08/single-linked-list-interview.html - 2.6