快慢指针（链表环检测 · 找中点 · Floyd 判圈）

快慢指针核心思想

• 快指针（fast）每次走 2 步
• 慢指针（slow）每次走 1 步
• 如果有环，快指针终将"追上"慢指针；否则快指针先到达末尾

链表中点（LeetCode 876）

ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;  // 奇数长度：正中间；偶数长度：后半的第一个
}

推导：设链表长度 n。循环结束时 fast 走了 2k 步，slow 走了 k 步。当 fast 到尾时，slow 恰在 n/2 处。

奇偶一致性：

n=5: 1→2→3→4→5→null
fast: 1→3→5→null，slow: 1→2→3  → 返回3（正中间）✓

n=6: 1→2→3→4→5→6→null
fast: 1→3→5→null（fast.next=6,fast=null退出），slow: 1→2→3→4 → 返回4（后半首节点）✓

用途：链表归并排序的中点切分。

环形链表（LeetCode 141）

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 到了末尾，无环
}

为什么一定会相遇：进入环后，设环长为 c。每轮循环 fast 比 slow 多走 1 步，相当于 fast 在环上追 slow，追 c 步后必然追上（距离模 c）。

环形链表 II：找环的入口（LeetCode 142）

这是 Floyd 判圈算法最精妙的应用，生产高频经典：

ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    // 第一阶段：找相遇点
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    if (fast == null || fast.next == null) return null;  // 无环

    // 第二阶段：找环入口
    slow = head;  // slow 回到头部，fast 留在相遇点
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;  // 两者同步走，相遇处即为环入口
    }
    return slow;
}

数学推导：

head ──────────── 入口 ──────── 相遇点
    <---- a -----> <--- b --->
                   <--- c ----> （环的剩余长度，b+c=环长）

相遇时：slow 走了 a + b
        fast 走了 a + b + n×(b+c)（多绕了 n 圈）
又因为 fast = 2×slow：
    a + b + n(b+c) = 2(a+b)
    a = n(b+c) - b = (n-1)(b+c) + c

当 n=1 时：a = c

结论：相遇后，一个指针从 head 出发、另一个从相遇点出发，同速前进，相遇处即为环的入口。

倒数第 N 个节点（LeetCode 19）

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;

    // fast 先走 n+1 步
    for (int i = 0; i <= n; i++) fast = fast.next;

    // 同步走，直到 fast 到末尾
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    // slow.next 就是待删节点
    slow.next = slow.next.next;
    return dummy.next;
}

为什么 dummy：如果删除的是头节点（n == 链表长度），dummy 节点避免空指针异常。

为什么先走 n+1 步（而不是 n 步）：让 slow 停在倒数第 n 个节点的前驱节点上，方便执行删除。

链表是否为回文（LeetCode 234）

结合快慢指针找中点 + 翻转后半 + 对比：

boolean isPalindrome(ListNode head) {
    // 1. 找中点
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 2. 翻转后半
    ListNode prev = null, cur = slow;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    // 3. 双指针比较
    ListNode left = head, right = prev;
    while (right != null) {
        if (left.val != right.val) return false;
        left = left.next;
        right = right.next;
    }
    return true;
}

时间 O(n)，空间 O(1)（不用额外数组，在链表本身操作）。

重排链表（LeetCode 143）

L0→L1→…→Ln 变为 L0→Ln→L1→Ln-1→…，综合运用三个子问题：

void reorderList(ListNode head) {
    // 1. 找中点
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 2. 翻转后半
    ListNode secondHalf = reverse(slow.next);
    slow.next = null;            // 断开前后两半

    // 3. 交叉合并
    ListNode first = head, second = secondHalf;
    while (second != null) {
        ListNode tmp1 = first.next, tmp2 = second.next;
        first.next = second;
        second.next = tmp1;
        first = tmp1;
        second = tmp2;
    }
}

ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

快慢指针 vs 对撞指针

数组中的快慢指针（非链表场景）

快慢指针也可以用于数组，等同于「原地过滤」：

// 找数组中重复的数字（LeetCode 287，类似 Floyd 判圈）
// 把 nums 视为「每个下标 i 指向 nums[i]」的链表，重复数即为环的入口
int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

无需修改数组，空间 O(1)，时间 O(n)——将 Floyd 判圈算法巧妙用于数组。