文章目录 缘起什么是快慢指针本文核心问题一：为什么快指针每次移动2，慢指针每次移动1？情况一：环为奇数情况二：环为偶数 问题二：如何判断环的入口结点和环大小 结束语reference
这篇博客讨论一下常见的快慢指针算法
缘起
自从刷leetcode以来，已经碰见过很多次应用快慢指针算法的题目了，但是每次都是直接刷过，并没有好好思考为什么要这么做，这篇博文来探讨一下快慢指针一些常见的问题，了解这些问题可能对你刷题并没有很大的帮助，但是会让你对快慢指针了解的更加深刻。
什么是快慢指针快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。
--------来自百度百科
上述描述了快慢指针算法的基本内容，其实了解这些东西，再看一个例题，差不多就可以开始利用快慢指针来解题了，但是本文探讨的是另外的问题。先来看个题理解一下快慢指针算法吧。
快慢指针的一类常见应用就是判断链表是不是含有环，如：141.环形链表。基本思路就是快慢指针遍历，如果相遇就表示有环，反之则没有。基本代码如下：
bool hasCycle(struct ListNode *head) { if(NULL == head) return false; struct ListNode *fast = head; struct ListNode *slow = head; while(slow && fast && fast->next){ slow = slow->next; // 慢指针每次走一步 fast = fast->next->next;// 快指针每次走两步 if(slow == fast) return true; } return false;} 本文核心 问题一：为什么快指针每次移动2，慢指针每次移动1？我看过的几乎所有的快慢指针的题解都是快指针每次移动2，慢指针每次移动1，这样毫无疑问是正确的，但是为什么呢？能不能快指针每次移动3呢？首先来分析一下快指针移动2，慢指针移动1的情况，
情况一：环为奇数
很明显，这个链表有环，分析一下slow和fast的指向的结点
slow：0、1、2、3、4、5、6、7
fast： 0、2、4、6、1、3、5、7
根据上面的值，两者在结点7时相遇，正好是慢指针转一圈（第一圈还没转完，但是为了便于描述采用这种方式），快指针转两圈的时候。
情况二：环为偶数
同样看一下slow和fast的值
slow：0、1、2、3、4、5、6
fast： 0、2、4、6、2、4、6
同样是快指针转两圈，慢指针转一圈。当然以上两种情况并不完整，但是已经足以说明问题。有兴趣的可以试试快慢指针都从环的入口结点进入环的情况，对应上图就是slow和fast第一个值都是1的情况。
回到正题，为什么会出现如上的情况呢，都是快指针转两圈慢指针转一圈的时候相遇呢？下面从数学方面解释一下：
假设链表无环部分结点有 m 个，环的结点个数为 n 个。慢指针走了 t 步之后与快指针相遇，那么慢指针在环中走的步数为 t - m ，快指针为 2t - m。此时快、慢指针必然是在环中；假设是在环入口后的第 x 个结点相遇，慢指针走了k1圈，快指针走了k2圈。则有
t - m = k1 * n + x
2t - m = k2 * n + x
加减消元求出 t = (k2 - k1) * n；也就是说慢指针走过n步后与快指针第一次相遇。这部分内容参考：证明 ：快慢指针可以判断单链表是否有环
再来看看快指针每次走三步，慢指针每次走一步的情况，以下面这个图为例：
slow：0、1、2、3、4、5、6、7
fast： 0、3、6、2、5、1、4、7
可以看出，仍然是慢指针经过 n 步之后与快指针第一次相遇，但是这时候的快指针已经走了三圈。可以验证快指针走四步，慢指针走一步的情况，还是会相遇，但是快指针转了四圈了。
从上面的分析可以看出，快指针可以不是2，但是为什么大家都喜欢写2呢？
先把上面的代码copy下来
bool hasCycle(struct ListNode *head) { if(NULL == head) return false; struct ListNode *fast = head; struct ListNode *slow = head; while(slow && fast && fast->next){ slow = slow->next;// 慢指针每次走一步 fast = fast->next->next;// 快指针每次走两步 if(slow == fast) return true; } return false;}我猜测是这样的，当选择快指针每次移动三个单位时，上面while循环的条件判断会增加，不然很可能（这里我想说一定的，但是有些特例不会）会报空指针错误。因此快指针每次移动2，慢指针移动1是一种比较好的思路。另外不要以为每次都是在环的最后一个结点相遇。
问题二：如何判断环的入口结点和环大小从上面问题一的讨论可以看出，取快指针为2，慢指针为1是比较好判断链表是否有环的方法。下面需要讨论的是，在链表有环的基础上如何找到环的入口。假设有如下链表。
先看一下slow和fast的值，slow和fast会在哪个结点相遇
slow：1、2、3、4、5、6、7
fast： 1、3、5、7、3、5、7
ok，slow和fast会在结点7相遇，而且很容易得到，下一次相遇也是在7这个结点。假设slow经过 t 步之后到达7，那么fast经过了 2t 步。而且可以肯定slow再经过 t 步之后还是在结点7这个位置，为啥？（t + t = 2t）。现在将fast重新移动到head处，即结点1所在位置，slow仍然指向结点7，然后slow和fast每次都前进一步（也就是fast和slow步长一样了），那么他们相遇的第一个结点就是环的入口。为什么？
上面已经说过了，slow是经过了 t 步之后到达7，并且slow再经过 t 步之后仍然是结点7。将fast移动到head之后，每次前进1，t 步之后会和slow重逢（相当于一开始的slow）。来看看slow和fast的路径：
slow：7、8、3、4、5、6、7
fast： 1、2、3、4、5、6、7
注意到了吗，3、4、5、6、7这一串是公共的路径，因此 3 就是环的入口结点。
分析到这一步之后，如果要求环的大小也很容易了。不用fast指向head，直接从第一次相遇的位置，fast和slow指向不变，fast每次移动2，slow每次移动1，设置个count，计算下次相遇经过了多少结点就可以了。
结束语到了这里，本文基本结束了，但是并不意味着这是快慢指针的全部内容，只是博主仅仅见识到了这些、仅仅想到了这些内容罢了，如果大家关于快慢指针还有啥有意思的问题，或者本文未曾提到的知识，欢迎留言和私信。我会尽量弄明白，并且按照情况更新到这篇文章中。
helping others is improving myself
leetcode – 287. 寻找重复数 ｜ 悲凉的毛衣的回答
证明 ：快慢指针可以判断单链表是否有环
快慢指针寻找环入口——学习笔记
快慢指针判断单向链表是否有环及找环入口
141. 环形链表