简介

快慢指针的解法在 LeetCode 中非常常见，尤其是涉及到链表有环的情况下。

我们常说的快慢指针解法，其实就是 Floyd 环形检测算法，这个算法会在链表的头部初始化两个指针，分别称为快指针和慢指针。慢指针每次走一步，快指针每次走两步。

也正是如此，这个算法也时常被称作龟兔赛跑算法。

本文主要讲解了快慢指针应对的四大题型：

是否有环

LeetCode 141: Linked List Cycle

用到两组指针：快指针和慢指针。快指针每次移动的速度是慢指针的两倍。

用代码表示如下：

1
2

fast = fast.next.next
slow = slow.next

快指针在某个点与慢指针相遇，那么链表存在环。

1

fast == slow

假设有个链表有环，如下图所示：

image.png

遍历三轮，快指针在第三次 travel 的时候与慢指针相遇，如下图所示：

image.png

环的长度

如果链表有环的话，怎么知道环的长度？还是先按照第一节的知识，让快慢指针进行相遇。

相遇后，让慢指针不动，新加入一个指针p放到相遇点。

  • 慢指针保持不动

  • p 绕着环遍历一圈，遍历一次计数加一

  • p 与慢指针相遇时，计数的值就是环的长度

image.png

环的起点

找到环的起点相对来说比较难，如果没有这方面的基础，很难第一次得到方案。

先说结论，基于第一节的内容，首先找到相遇点。在链表的头部新加入一个指针 p。

p 和相遇点的慢指针再次同速度地进行遍历，每次移动一个元素。

p 和慢指针的相遇点，就是环的起点。

image.png

快指针与慢指针相遇时，分别走了多长？

如图所示，入环前的长度为 a， 入环点到相遇点 为 b, 相遇点再此到入环点为 c

根据相遇条件可以得到以下结论：

  • 快指针速度快，当快慢指针相遇时，快指针要多走一个环。

  • 快指针速度为慢指针的 2 倍，走过的长度也是 2 倍

  • 快指针走过的长度为 a + b + c + b

  • 慢指针走过的长度为 a+b

有了这个知识后，可以得到 a+b+c+b = 2(a+b)

最终得到一个比较重要的等式: a=c

如何找到入环点

有了上面的知识后，那么可以得出：

如果在相遇点顺时针遍历到入环点的长度，等于链表头部走到入环点的长度

那么就可以在相遇点的基础上，在链表头部放入一个新指针 p，p 每次遍历一个节点。同时慢指针也从相遇点开始遍历。当 p 与慢指针相遇时，这个相遇点就是入环点

image.png

287 这道题的典型代表就是，将数组当成链表操作。

环的移除

找到入环点或者找到重复的数(#287)已经很难了，移除环那就显得更难了。

但如果在找到了入环点的前提下，环的移除就引刃而解了。

  • 找到快慢指针相遇点

  • 新建一个慢指针放到链表头部

  • 新慢指针和慢指针相遇点，就是入环点，记住入环点的前一个位置

  • 将入环点的前一个节点指向 nil

image.png