快慢指针：原理、图解与 C++ 实战

一、什么是快慢指针

快慢指针（Fast & Slow Pointers）是链表题中最经典的双指针技巧，又叫 Floyd's Tortoise and Hare（龟兔赛跑算法）。它设置两个指针同时从头节点出发，但移动速度不同：

• 慢指针（slow，龟）：每次走 1 步
• 快指针（fast，兔）：每次走 2 步

它的典型应用几乎都集中在链表上：

二、核心原理与图解

快慢指针的核心思想可以浓缩成两个直觉："速度差导致追逐" 和 "速度比决定位置关系"。下面分四个场景图解。

2.1 速度差：线性链表上的追逐

在线性链表上，快指针每轮比慢指针多走 1 步。所以两者的距离每轮扩大 1。当快指针走到末尾（nullptr）时，慢指针恰好位于链表中部。这就是"找中点"的原理。

2.2 环检测原理：为什么一定会相遇

如果链表有环，快指针永远不会走到 nullptr，而是会在环里无限转圈。关键问题是：快指针一定能在环里追上慢指针吗？

答案是一定。把目光聚焦到慢指针刚进入环的那一刻：此时快指针已经在环里某处。之后每走一轮，快指针比慢指针多走 1 步，也就是两者在环上的距离每轮缩小 1。距离从某个有限值开始，每轮减 1，最终必然减到 0——即相遇。

2.3 找链表中点：速度比决定位置

当快指针走到链表末尾时，慢指针走过的步数恰好是快指针的一半。因为快指针走的总步数 ≈ 链表长度，所以慢指针刚好停在链表中点。

2.4 Floyd 判圈算法：两个阶段

找环入口的完整 Floyd 算法分两个阶段：

1. 阶段一（相遇）：快慢指针同速出发，慢走 1、快走 2，在环内某点 M 相遇。
2. 阶段二（找入口）：把一个指针重新放回头节点，另一个留在 M，两者都改为每次走 1 步，再次相遇的位置就是环入口 E。

2.5 复杂度分析

三、通用模板

快慢指针的代码极简，掌握下面两个模板就能覆盖绝大多数场景。

3.1 模板一：环检测（返回是否有环）

// 链表节点定义（所有题目通用）
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 模板一：判断链表是否有环
bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {      // fast 能走才继续
        slow = slow->next;            // 慢走 1 步
        fast = fast->next->next;      // 快走 2 步
        if (slow == fast) return true; // 相遇 = 有环
    }
    return false;                      // fast 到 ∅ = 无环
}

3.2 模板二：找链表中点

// 模板二：返回链表的中间节点
// 偶数个节点时返回靠右的那个中间节点
ListNode* middleNode(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {       // fast 还能走 2 步就继续
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;                        // fast 到尾，slow 在中点
}

四、示例一：环形链表（LeetCode 141）

题目（LeetCode 141）：给定一个链表的头节点 head，判断链表中是否有环。如果链表中存在环，返回 true；否则返回 false。

4.1 思路

直接套用模板一：快慢指针同起点出发，慢走 1、快走 2。若快慢指针相遇则一定有环（参见图 2）；若快指针走到 nullptr 则无环。

以链表 1→2→3→4→5，其中节点 5 的 next 指回节点 3（形成 3→4→5→3 的环）为例，追逐过程如下：

4.2 C++ 代码

#include <stdbool.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head) return false;          // 空链表必无环

        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;          // 慢指针走 1 步
            fast = fast->next->next;    // 快指针走 2 步
            if (slow == fast) {
                return true;         // 相遇，存在环
            }
        }
        return false;                  // fast 走到末尾，无环
    }
};

五、示例二：环形链表 II（LeetCode 142）

题目（LeetCode 142）：给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，返回 nullptr。

5.1 数学推导

这是 Floyd 算法的完整版。设（参见图 6）：

• a：头节点到环入口 E 的距离
• b：从 E 沿前进方向到相遇点 M 的距离
• c：从 M 沿前进方向回到 E 的距离（即环长 = b + c）

推导过程：相遇时慢指针走了 a + b，快指针走了 a + b + n(b+c)（n 为快指针多绕的圈数，n ≥ 1）。由 fast = 2 × slow：

最后这个式子说明：从 head 走 a 步 = 从 M 出发走 c 步再绕 (n-1) 整圈，两者都会到达环入口 E。所以阶段二把一个指针放回 head、另一个留在 M，都改为每次走 1 步，它们必然在 E 相遇。

5.2 C++ 代码

#include <cstddef>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;

        // 阶段一：快慢指针找相遇点
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                // 相遇，进入阶段二：找环入口
                ListNode *p = head;
                while (p != slow) {       // 两个都走 1 步
                    p = p->next;
                    slow = slow->next;
                }
                return p;               // 再次相遇 = 环入口
            }
        }
        return nullptr;                 // 无环
    }
};

六、示例三：链表的中间结点（LeetCode 876）

题目（LeetCode 876）：给定单链表的头节点 head，返回链表的中间节点。如果有两个中间节点，返回第二个中间节点。

6.1 思路

套用模板二。快指针走到末尾时，慢指针恰好在中间。对于偶数个节点，由于循环条件是 fast && fast->next，快指针会停在最后一个节点（fast->next 为空时停止），此时慢指针正好停在靠右的中间节点，符合题目要求。

6.2 C++ 代码

#include <cstddef>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {     // fast 还能走 2 步就继续
            slow = slow->next;        // 慢走 1
            fast = fast->next->next;  // 快走 2
        }
        return slow;                  // fast 到尾，slow 即中点
    }
};

七、总结与适用场景

典型题目清单

• LeetCode 141：环形链表（环检测，基础）
• LeetCode 142：环形链表 II（找环入口，进阶）
• LeetCode 876：链表的中间结点（找中点，基础）
• LeetCode 19：删除链表的倒数第 N 个结点（快慢指针拉开距离）
• LeetCode 234：回文链表（找中点 + 反转后半段）
• LeetCode 143：重排链表（找中点 + 反转 + 合并）
• LeetCode 148：排序链表（找中点 + 归并）
• LeetCode 287：寻找重复数（Floyd 判圈在数组上的妙用）