LeetCode：链表中是否存在环的证明问题。
判断链表中是否存在环，通常使用双指针的方式，因为快指针、慢指针最终都会在环中相遇，但如何证明这两个指针一定会相遇呢，推倒过程如下：
我的疑问是：算式（3）是通过怎样的方式转换为算式（4）的呢？
------------------------分割线------------------------
反向证明如下：
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我们的思路就是：设置两个快慢指针（快慢指针即两个指针起点相同，慢指针每次走一步，快指针走两步），让它们一直往下走，直到它们相等，说明有环。下面简单证明，
如上图，A 为链表第一个结点，B 为环与链表的交叉点，C 为快慢指针相遇的位置。假设环的长度为 r，则有
$$
\frac {AB+BC+n_1r}{2}=AB+BC+n_2r\tag{左为快指针，右为慢指针}
$$
其中，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 \tag{其中 $n=n_1-2n_2$}
$$
这个证明很简单。对于任意两个满足条件的不同的 n 值，一小一大，相比较而言，它们计算出的两个 BC 值的差值一定是整除 r 的，所以 C 点必定唯一。
转自：https://ethsonliu.com/2019/08/single-linked-list-interview.html - 2.6
(a + b) % c = (a % c + b % c) % c这个证明把
() % c部分约掉了。