快慢指针：移除、找中点与判环

快慢指针是双指针里最"省空间"的形态：两个指针同向而行，fast 负责探路，slow 负责记账，全程不需要额外数组。本文把三个最经典的应用放在一起对比，会发现它们是同一个思想在不同数据结构上的投影。

场景一：原地移除元素（27）

题目：原地删除数组中所有值等于 val 的元素，返回新长度。

暴力做法是发现一个删一个、把后面整体前移，最坏 O(n²)。快慢指针换一个角度：fast 只负责扫描判断，slow 指向"下一个可写入的位置"。

数组：0 1 2 3 2 4    (val = 2)

fast：  0✓写  1✓写  2✗跳  3✓写  2✗跳  4✓写
slow：  0→1  1→2  2(停)  2→3  3(停)  3→4

数组变为：0 1 3 4 | 2 4   （竖线后是残留数据，题目不关心）
返回 slow = 4，即新长度

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;                        // 下一个可写入的位置
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {         // fast 探到该保留的元素
                nums[slow++] = nums[fast];   // 写入 slow 位置
            }
        }
        return slow;                         // slow 恰好就是新长度
    }
}

这个"快探慢写"模板是通用的：283 移动零（非零数前移再补零）、26 删除有序数组中的重复项，都只是换一个判断条件。

场景二：链表找中点（876）

fast 每次走 2 步，slow 每次走 1 步，fast 到头时 slow 恰好在中间：

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;        // 1 步
            fast = fast.next.next;   // 2 步
        }
        return slow;
    }
}

步长 2:1 意味着 fast 走完全程时 slow 恰好走了一半：

• 奇数长度：slow 停在正中间的节点。
• 偶数长度：slow 停在中间偏后的节点（返回的是第二个中点，876 正是这个要求）。

while 条件必须是 fast != null && fast.next != null，且顺序不能反，否则 fast 为 null 时先访问 fast.next 会空指针。

场景三：链表判环（141）

fast 走 2 步、slow 走 1 步，只要链表有环，两者一定会在环内相遇：

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;   // 在环内追上
        }
        return false;                        // fast 走到头，无环
    }
}

为什么必然相遇？

分两段看：

1. fast 一定能进入环：只要存在环，步长大的 fast 必然先于（或同时）进入环。
2. 进环后必然追上：以 slow 为参照物，fast 每走一步相对靠近 1 个节点（2 - 1 = 1）。设进环瞬间两者在环内相距 d（d ≥ 1），每走一步 d 减 1；d 是有限值，迟早减到 0——相遇。

关键在于"每次恰好靠近 1"：距离逐格递减，不会出现一步跨过 slow 的情况。这也是步长差必须为 1 的原因：若 fast 走 3 步、slow 走 1 步，相对步长为 2，在偶数环长下可能永远互相错过。

三大场景对比

一个有意思的对比：移除元素里两个指针步长都是 1，差别在于"写不写"；链表的两个场景里差别在步长本身。前者制造的是空间上的错位，后者制造的是时间上的错位——同一思想的两种投影。

易错点

• 27 里 slow 初值写成 -1 或返回 slow - 1：slow 的语义就是新长度，初值 0、直接返回 slow。
• 876 的 while 条件把 fast.next != null 写在前面：短路顺序反了，fast 为 null 时先解引用直接 NPE。
• 141 的相等判断放在移动之前：初值都是 head，第一轮就"相遇"，直接误判成有环。
• 142 找入环点：相遇后让一个指针回到 head，两个指针每次各走 1 步，再次相遇处即入环点；这一步的数学推导（头到入环距离 = 相遇点绕环到入环距离）值得自己写一遍。

题目清单

参考

• 代码随想录 · 双指针法专题