【leetcode】快慢指针 | Ruixiang's blog

什么是快慢指针？快慢指针是遍历操作时的一种技巧，通常是由一个快指针和一个慢指针组成，一般应用在链表操作上。

什么是快慢指针？

应用场景

• 判断链表是否有环：
此时需要快慢指针来判断，当快慢两个指针都进入环内时，可以想象成两个人在操场跑圈，一个人的速度是另外一个人的两倍，跑了若干圈后，快的人总会在某个时间点和慢的人相遇，只要有速度差就会相遇，除非两个人速度一致都保持相对静止。所以当链表存在环时，快慢指针同时从起点出发，总会在某个时刻相遇。

• 求有环链表环的起点：
这个思路也是利用快慢指针，不过稍微复杂一点，需要我们在这里简单做一个数学证明。假设链表在某一点有环，此时从 head 到这个节点的距离为 ，环的周长设为 ，我们知道当快慢指针都进入环内进行循环跑动时，总会在某一点相遇，那么在相遇时快指针一定比慢指针多跑了 圈（ 为整数），多跑的长度为 。 令 为快指针跑过的距离， 为慢指针跑过的距离，因为 恒成立且 推出 。注意，此时 和 都不一定处于环的入口节点处，因为要想到达环的起始结点处还必须得跑 的距离， 使得 , 这样才符合慢指针从链表起点出发，先跑过 进入环内，再跑了 圈后又回到环的入口结点的条件。所以我们需要再提前保留一个指向链表头节点的指针，在快慢指针已经相遇的条件下，移动它，慢指针也跟着一起走，当它走过 的距离来到环的入口结点时，慢指针走过的距离也变成了 , 也来到了环的入口结点处，两个指针相遇，此时指向的结点就是环的入口结点。

• 相交链表
这道题的思路也较为奇特，虽然只是一道简单题，但是没有发散思维或者链表成环意识的话一时半会也很难想到。A 链表和 B 链表相交于某一点或者不相交，如果相交的话可以认为一个链表前半部分分叉成 A 和 B 两部分。这时候需要双指针 指针 A 和 指针 B，而非快慢指针。指针 A 从 A 的头结点开始出发，当走到末尾时就指向 B 的头节点，指针 B 从 B 的头节点开始出发，当走到末尾时指向 A 的头节点。原理：假设 A 和 B 相交前的长度分别为 和 ，相交后的长度为 ， 当指针 A 走过 的距离时第二次回到了相交点， 此时指针 B 走过的距离为 （指针 A 和指针 B 同速），所以也到达了相交点，指针 A 和指针 B 相遇。

• 删除链表的倒数第 N 个节点
双指针，一个领先另一个 N 个节点，比较直观