快慢指针及其应用

前言

         计算机算法是一门非常有意思的科学，经常研究算法能激发我们大脑的潜能，使我们的大脑变得越来越灵活，思考问题变得更加敏捷和全面。本文是我学习快慢指针相关知识的一个读书笔记，包含快慢指针的应用例子，及快慢指针在这个例子中的应用为什么会正确的逻辑推导。在算法方面，我也是一个初学者，以前也没有深入的，专门的研究过，如果文章中有错误的地方，希望留言指正，大家一同学习，共同进步。

提示：以下是本篇文章正文内容，下面案例可供参考

一、什么是快慢指针

         快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动两步，慢指针每次向前移动一步。快慢指针的定义就那么简单，后面会给出一个例子：利用快慢指针判断单列表是否有环，查找环的入口节点，以及使用数学方程式证明查找方式的正确性。

二、快慢指针的应用

1.题目描述

给定一个链表，如果有环路，找出环路的开始点。

2.输入输出样例

         输入是一个链表，输出是链表的一个节点。如果没有环路，返回一个空指针。.

         在这个样例中，值为 2 的节点即为环路的开始点。链表节点定义如下：

struct ListNode { 
      int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) { 
     } }; 

3.解题思路

         对于链表是否存在环的问题，有通用的解决方法，即快慢指针。定义两个指针，快指针命名为fast，慢指针命名为slow，它们同时指向链表的开头。快指针每次前进两步，慢指针每次前进一步。如果快指针能走到尽头，则链表没有环；如果快指针无限走下去，且某一时刻和慢指针相遇，那么这个链表一定有环。
         上面的思路我们可以断定链表是否有环，那么，环的入口节点应该如何确定？这个很简单，当快慢节点首次相遇后，我们把快指针指向链表开头，且每次只前进一步；慢指针继续从相遇点开始，保持每次前进一步，那么，当快慢指针第二次相遇时，相遇的节点即为环的入口节点。

4.代码实现

struct ListNode { 
      int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) { 
     } }; ListNode* find_enter_of_cycle(ListNode* head) { 
      ListNode* slow = head; ListNode* fast = head; // 第一步：判断是否有环 do { 
      if (fast == nullptr || fast->next == nullptr) return nullptr; //快指针走到了尽头，表示没有环 fast = fast->next->next; //快指针每次前进两步 slow = slow->next; //慢指针每次前进一步 } while (fast != slow); //相遇则退出，表示有环 // 第二步：找出环的入口节点 fast = head; //快指针重新指向链表开头 while (fast != slow) { 
      //再次相遇时结束查找，相遇点即为环的入口节点 slow = slow->next; //快指针每次前进一步 fast = fast->next; //慢指针每次前进一步 } return fast; } 

5.逻辑推导

         上面的解题思路中，步骤一：判断链表是否有环，这个思路比较简单，很好理解，没有疑问。但是步骤二：通过快慢指针每次都走一步，再次相遇时的节点为环的入口节点，这个查找方法不好理解，并不能直观的确定这种方法是否正确。
        在学习这个算法解题思路的时候，我也是非常好奇，为什么第二次相遇的位置一定是环的入口节点呢？为什么不会是别的节点，会不会永不相遇，程序陷入死循环呢？带着这个疑问，我在草稿上画了一个图形，使用数学方程式的方法来证明算法步骤二的正确性，通过方程式运算，终于解开了心中的疑问。
         下面，通过自己绘制的一张丑陋的图及简单的数学方程式运算步骤，来证明快慢指针第二步找入口点的正确性。

上图中各部分的说明：
节点1为链表头；
节点2为链表中，环的入口节点；
节点3为链表中，快慢指针首次相遇的节点；
节点4为链表中，下一个节点为入口节点的位置，如果没有环，则这个点为终点；
x：表示从头节点到环的入口节点的步数；
y：表示环的入口节点到快慢指针首次相遇的那个节点的步数；
z：表示从快慢指针第一次相遇的点开始，到环入口节点2的步数。

 
简单逻辑推导步骤：
1、在查找是否有环的过程中，快指针每次走两步，慢指针每次走一步，那么第一次相遇时，快指针走的步数是慢指针步数的两倍，所以，存在这样一种关系：令n表示相遇前，快指针在环中走完整个环的次数；走完一环需要（y+z）步，数学恒等式如下：（快指针在相遇点开始，绕了n次环，加上x+y即为快指针走的步数）

//慢指针步数的两倍，和快指针走的步数一样多 2*(x+y) = x + y + n*(y+z) 

2、在查找入口节点过程中，快指针重新从链表头开始走，每次前进一步；慢指针从第一次相遇点开始，继续以每次一步的速度向前走。两个指针走的步数是一样的。 如果需要快慢指针相遇，它们一定在节点2处相遇（环的入口节点），否则，在移动速度相同的情况下，它们将永远不会再相遇。我们只需要证明：从首次相遇节点（节点3）开始，慢指针走过x步后一定处于2号节点处即可。（快指针走x步一定是在节点2处的）

//1、如果慢指针从节点3开始走，第一次走到节点2就遇到快指针，则有 x = (y + z) - y;//差y步就走完一圈 //2、如果慢指针从节点3开始走，走过完n-1次完整的环后回到节点3，然后继续往前走（第n圈）到节点2与快指针相遇，则有 x = n*(y + z) - y;//差y步就走完n圈。 

现在只需证明x = n*(y + z) – y就可以证明快慢指针一定在节点2处相遇了。 从步骤一的恒等式可以得到以下推导结果：

//方程式变换 2*(x+y) = x + y + n*(y+z); ==> x = n*(y+z) - y; 

我们用方程式推导出了x = n*(y+z) – y，就证明了快慢节点一定在节点2处相遇，节点2表示环的入口节点，这样我们最终证明了快慢指针第二次相遇的地方即为环的入口点，相遇后，快慢指针将永远指向相同的节点。
我们可以从恒等式 x = n*(y+z) – y和图结合在一起，很容易看出以上的结论是正确的：
当n=1:
x = z；从图上看，慢指针走z步到了节点2，快指针走了x步也刚好到了节点2；
以此类推,m是任意正整数
n = m：
x = m*(y+z) – y。//假设n等于任意正整数m时等式成立
n = m + 1：
x = m*(y+z) – y + (y+z) ==>x = m*(y+z) + z ==>x=(m+1)(y+z)-y //m+1时等式也成立（慢指针再多走一圈时,快慢指针在节点2相遇）
 

归纳总结：快指针走x步，慢指针走n*(y+z) – y步，快慢移动速度相同时一定存在：x=n*(y+z) – y；对于快指针，走x步刚好到达节点2，对于慢指针，走过n*(y+z) – y步后，也恰好到达节点2。结论：快慢指针相遇点为环的入口节点。

总结

在看快慢指针之前，我的解题思路是容器存着已遍历的节点指针，边遍历，边查找容器，如过下一个节点在容器内，则这个节点即为环的入口节点。这样的解题思路是以空间换时间，对于节点数非常巨大的链表，这种方法显然非常笨拙。使用快慢指针，我们对空间的消耗非常少，查找的代码也非常简单明了，缺点是不太好理解。
本文关键词：
1、快慢指针的概念；
2、判断单链表是否有环；
3、查找有环单链表的环的入口位置；
4、数学归纳法找单链表的环的入口节点。