【双指针技巧】链表与快慢指针专题
快慢指针
快慢指针是链表问题中双指针技巧的一种典型应用。它通过让两个指针以不同的速度移动，利用它们之间的位置关系来解决一些链表问题。
链表的中间节点
这道题要求我们找到链表的中间节点（距离链表头部 n/2 个节点的位置）。
一个很自然的思路是，先遍历一遍链表，求出链表的长度 n。
知道链表长度之后，中间节点的位置也就确定了：只需从 head 开始，向后走 n / 2 步，就可以找到题目要求的中间节点。
复盘一下，我们不难发现这种思路需要遍历两趟链表，分别在求链表长度以及找到中间节点时各遍历了一次。
其实，本题存在一种只需要遍历一趟的解法。我们不妨换一个方式，重新审视这个问题。
假如有一段长度未知的距离：
▼text复制代码A -------------------------------- B
现在就你一个人，我需要你精确找到 AB 这一段的中点。你自己想想，这个任务能圆满完成吗？
显然不能。
因为事先不知道 AB 的长度，所以即使知道自己已经从 A 走了多远，也无法判断这段距离占 AB 全程的多少，自然无法确定自己是否走到了中点。
既然一个人无法在不知道总长度的情况下确定中点，我们可以尝试增加一个人，让他作为前一个人的参照。
现在，我们让两个人都从 A 出发，其中一个人的任务仍然是找到 AB 的中点，而另一个人则负责走完 AB 全程。
接下来就需要考虑这一问题：这两个人要按照什么样的节奏前进，才能同时完成各自的任务？
我们先明确两个人各自需要走多远。
第一个人的目标是 AB 的中点，也就是说，当任务完成时，他只需要走完 AB 的一半；第二个人的目标是 B，也就是说，他需要走完整个 AB。
由于两个人同时从 A 出发，我们可以把第二个人到达 B 的时刻作为判断中点的时刻。此时，两个人经过的时间相同。
根据公式： $$ 路程 = 速度 × 时间 $$ 在时间相同的情况下，走过的路程与速度成正比。由于第一个人走了 AB 的一半，第二个人走了完整的 AB，因此第二个人的速度应该是第一个人的 2 倍。
于是，我们可以让一个人每次向前移动 1 个单位的距离，另一个人每次向前移动 2 个单位的距离。
那么，回到链表中，我们应该如何理解这里的**“一个单位的距离”**呢？
链表是离散结构，我们每次沿 next 只能前进到下一个节点，所以沿 next 前进一步，就记作一个单位的距离。
于是，前面的结论就可以具体实现为：一个指针每次沿 next 前进 1 次，另一个指针每次沿 next 前进 2 次。
基于上述思路，我们不难写出如下代码：
▼java复制代码public ListNode middleNode(ListNode head) { ListNode p = head, q = head; while (q != null && q.next != null) { p = p.next; q = q.next.next; } return p; }
上述操作只需遍历一趟链表，因此时间复杂度为 $O(n)$。
我们刚才让两个指针以不同的速度移动：一个指针每次沿 next 前进 1 次，另一个指针每次沿 next 前进 2 次。
在链表问题中，这种通过两个移动速度不同的指针来解决问题的方法，就称为快慢指针法。
环形链表 Ⅰ
前面我们已经通过快慢指针解决了链表中点问题。接下来，我们来看看它是如何解决环形链表相关问题的。
本题需要我们判断给定链表中是否存在环，例如这样一个链表：
在链表没有环的情况下，我们可以正常从头走到尾。但是，一旦链表中存在环结构，此时我们永远也无法走到 null。
那么，在不知道链表是否存在环的情况下，我们如何判断自己是不是一直在环中兜圈子？
这个问题其实很容易想到一种直接的解决方案：记录自己已经经过的节点。
我们可以维护一个 Set 集合，用于存储遍历过程中经过的节点。每遍历到一个新的节点，就将其加入 Set。如果当前遍历到的节点已经在 Set 中，说明我们之前已经经过这个节点，而现在又重新回到了这里，那么就可以判断链表中存在环。
反过来，如果最终遍历到了 null，说明链表中不存在环。
分析一下此方案的时间复杂度，由于每个节点最多只会被遍历一次，而 Set 的 add 和 contains 操作平均时间复杂度都是 $O(1)$，因此总的时间复杂度是 $O(n)$。
但是这种方案需要维护 Set 集合，最坏的情况下，链表的 n 个节点都要进入 Set 中，因此空间复杂度为 $O(n)$。
这个方案虽然能奏效，但是题目最后提出了一个进阶要求：能否使用 $O(1)$ 的空间复杂度解决这个问题？
如果要求空间复杂度为 $O(1)$，那么我们就不能再像刚才那样，用 Set 记录所有经过的节点。那么，还有没有其他办法判断自己是不是已经绕了一圈？
我们还是先从一个人想起。如果只有一个人沿着链表不断向后走，那么当他再次经过某个节点时，他自己其实并不知道自己之前是否来过这里。因为他没有记录，也没有其他东西可以作为参考。
既然一个人无法判断自己是否一直在环中兜圈子，那么我们可以尝试增加一个人。
此时，就好比两个人在一个环形跑道上赛跑。如果一个人速度慢，另一个人速度快。那么我们显然可以知道：在将来的某个时刻，两个人一定会再次相遇。
一个人跑得快、一个人跑得慢……欸？等等！！这不就和我们前面遇到过的快慢指针极其类似么？没错，快慢指针法正是解决这个问题的关键。
然而，我们现在只知道，快慢指针需要两个速度不同的指针，至于当前问题具体应该采用怎样的速度关系，我们目前并不知道。
在寻找链表中间节点这一问题中，我们曾经推导出 $1:2$ 的速度关系。但那个结论是为了找到中点而得到的，到了这个问题，我们不能想当然地认为它仍然成立。（虽然它确实成立，而且很多题解和代码模板也都是直接告诉你 ”快 2 慢 1“ 的结论）。
这一次，我们不去套用已有的结论，而是从头推导为什么这里继续沿用 $1:2$ 的速度关系。
我们先考虑一般化，设：
- 链表中存在环；
- 慢指针每次走 $a$ 步，快指针每次走 $b$ 步；
- 快慢指针的相对速度 $d = b - a$；
- 环长为 $L$。
因为快指针更快，所以快指针一定先进入环。当慢指针也进入环后，以慢指针第一次进入环的时刻为起点。
此时把慢指针所在的那个节点，记为环上的位置 0。从该节点出发，沿链表前进方向把环上的节点依次编号为：
$$ 0,1,2,...,L - 1 $$ 设快指针在编号为 $k$ 的位置，其中： $0 ≤ k ＜ L$
此后经过 $t$ 轮后，慢指针所在编号为：
$$ t \cdot a \pmod L $$
快指针所在编号为：
$$ k + t \cdot b \pmod L $$
二者要相遇，当且仅当：
$$ k + t \cdot b \equiv t \cdot a \pmod L $$
移项：
$$ t \cdot (b-a) \equiv -k \pmod L $$
即：
$$ t \cdot d \equiv -k \pmod L $$
这是一个关于 $t$ 的同余方程。在数论中，这个同余方程有解，当且仅当： $$ \gcd(d,L) \mid k $$
gcd 即最大公约数，此式子读作：
gcd(d,L)整除k。
也就是说：
- 若 $\gcd(d, L) = 1$，则无论 $k$ 是多少，方程都有解，因此二者最终一定能够相遇。
- 若 $\gcd(d, L) ＞ 1$，则只有当 $k$ 是 $\gcd(d,L)$ 的倍数时，方程才有解；否则方程无解，二者永远不会相遇。
然而我们事先既不知道环长 L，也不知道慢指针进入环时快慢指针之间的相对位置 k。为了让判环算法对任意链表都成立，就必须保证对于任意可能的 L 和 k，上述同余方程都有解，就必须满足：
$$
\gcd(d,L)=1
$$
进一步地，如果要求它对任意正整数 L 都成立，那么 d 必须与所有正整数互质。正整数中只有 1 满足这一条件，因此 $d = 1$。
$d = 1$ 只确定了快指针只比慢指针多走 1 步，而满足这个条件的组合有很多，例如：
- 慢指针每次走 1 步，快指针每次走 2 步；
- 慢指针每次走 2 步，快指针每次走 3 步；
- 慢指针每次走 3 步，快指针每次走 4 步；
- ...
但通常取 “慢指针每次走 1 步，快指针每次走 2 步” 这一策略。
随便举个例子你就明白了。假如你头铁，非要选 “慢指针每次走 3 步，快指针每次走 4 步” 这一策略。你在真正移动之前，还需要进行一系列判空，例如：
▼java复制代码while (fast != null && fast.next != null && fast.next.next != null && fast.next.next.next != null) { slow = slow.next.next.next; fast = fast.next.next.next.next; }
这样的代码你能接受么？
而 $a=1,b=2$ 时，代码实现起来会更简单：
▼java复制代码while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
更重要的是，慢指针每次走 1 步，能保证它不会跳过链表中的任何一个节点。
如果慢指针一次走 2 步或 3 步，虽然对于单纯的“判环”来说，只要相对速度为 1，最终仍然可以相遇，但我们在后续问题中往往还需要利用指针的具体位置关系，例如寻找环入口。此时，前面基于“慢 1、快 2”推导出的距离关系就不能直接使用了。因此，“慢 1 快 2”是最稳妥、最通用的选择。
经过上述大段论述，我希望你能明白：“让快指针每次走2步，慢指针每次走1步” 不再是轻飘飘的模板结论，而是对实现简单性和后续可复用性进行权衡后得到的最自然选择。
基于上述思路，我们不难写出如下代码：
▼java复制代码public boolean hasCycle(ListNode head) { ListNode fast = head, slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { return true; } } return false; }
上述操作只需遍历一趟链表，因此时间复杂度为 $O(n)$。
环形链表 Ⅱ
前面我们已经通过快慢指针解决了链表是否存在环的问题。接下来，我们继续思考一个更进一步的问题：环形链表 Ⅱ
本题不再只是要求我们判断链表中是否存在环，而是要求我们找到环的入口节点。
例如，对于下面这个链表：
如果链表存在环，那么我们最终需要找到的，就是图中标红的这个节点。
在上一题中我们已经知道，让慢指针每次走 1 步、快指针每次走 2 步，可以保证二者最终在环中相遇。这一次，我们就从这个第一次相遇的位置出发，重点推导第一次相遇时，快慢指针与环入口之间存在怎样的距离关系。
我们设以下变量：
- 链表头到环起点的距离为 $x$；
- 从环起点沿链表前进方向走到相遇点的距离为 $y$；
- 从相遇点沿链表前进方向走到环起点的距离为 $z$。
不难得知环长 $L = y + z$，对应图示：
▼text复制代码head ──x──▶ 环起点 ──y──▶ 相遇点 ▲ │ └──── z ───────┘
相遇时，慢指针走过的距离为： $$ x + y $$ 由于快指针更快，所以二者相遇时，快指针除了走过与慢指针相同的 $x+y$ 外，还会在环中多绕若干整圈。因此其走过的距离为： $$ x + y + nL $$
其中 $n \ge 1$，表示快指针比慢指针多绕的整圈数。
由于快指针的速度是慢指针的 2 倍，所以总路程有以下关系： $$ 2(x + y) = x + y + nL $$ 化简： $$ x = nL - y $$ 代入 $L = y + z$ ，并整理： $$ x = (n - 1)L + z $$ 这个式子说明了什么？
这个式子说明：从相遇点出发走 x 步，会先经过 z 步到达环起点，然后再绕环 (n-1) 圈。
这一结论非常有趣且重要。想想看，如果我们把其中一个指针从相遇点拉回 head，然后快慢指针都按照 “每次走一步” 的步伐走下去。
在二者各走了 $x$ 步过后，会再次在哪相遇？—— 环起点呀！！！
你想想是不是这样？
基于上述思路，我们不难写出如下代码：
▼java复制代码public ListNode detectCycle(ListNode head) { ListNode fast = head, slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } } return null; }
上述操作中，两个阶段的指针移动次数总计为 $O(n)$，因此时间复杂度为 $O(n)$。
