双指针技巧汇总

1.判定链表中是否含有环

快指针走两步，慢指针走一步：
快指针走到null，无环
两个指针相遇，有环

为什么有环二者一定会相遇？

这里给出我的理解。以下图这个有环的链表为例，

从“快指针和慢指针同时从链表的头结点出发”到“快指针最终和慢指针相遇”，这中间的过程可以分为两个阶段：“无聊的第1阶段：快指针、慢指针一起往前跑”和“精彩的第2阶段——快指针追慢指针”。

在“无聊的第1阶段：快指针、慢指针一起往前跑”中，快指针和慢指针一起往前跑，每一次快指针往前跑两步、慢指针往前跑一步，直到快指针出现在慢指针的后面，具体请看下图。

无聊的第一阶段

在“精彩的第2阶段——快指针追慢指针”中，

对于链表有环的情况，为什么快慢指针一定会相遇？快慢指针一定会相遇的精髓在于：当“快指针出现在慢指针后面”之后，每一次“快指针往前走两步、慢指针往前走一步”，相当于快指针和慢指针之间的相对距离减少1步。

假如说，当快指针刚刚绕到慢指针后面时，快指针离慢指针有n步。那么，对于接下来的每一次“快指针往前走两步、慢指针往前走一步”，快指针和慢指针之间的距离由n步变成n-1步、由n-1步变成n-2步、……、由3步变成2步、由2步变成1步、由1步变成0步。

所以对于有环的情况，快慢指针一定会相遇。
转自：https://editor.****.net/md?not_checkout=1&articleId=109209104