一、 数学证明

我们可以通过建立数学模型来证明：如果链表中存在环，快慢指针一定会相遇；如果不存在环，快慢指针永远不会相遇。

1. 模型假设

• 设链表起点到环入口点的距离（节点数）为 $a$（$a \ge 0$）。
• 设环的长度（环中的节点数）为 $b$（$b \ge 1$）。
• 设慢指针（Slow）每次移动 1 步，快指针（Fast）每次移动 2 步。
• 设 $t$ 为移动的步数（或时间）。

2. 指针位置的数学表达

• 慢指针在时刻 $t$ 的位置 $S(t)$： 当 $t \ge a$ 时，慢指针已经进入环内。它在环内的相对位置（距离环入口的步数）为： $$(t - a) \pmod b$$

• 快指针在时刻 $t$ 的位置 $F(t)$： 当 $2t \ge a$ 时（显然在慢指针进入环时，快指针早已进入环），快指针在环内的相对位置为： $$(2t - a) \pmod b$$

3. 相遇条件

快慢指针相遇，意味着它们在环内的相对位置相同： $$S(t) \equiv F(t) \pmod b$$

代入位置公式： $$(t - a) \equiv (2t - a) \pmod b$$

两边同时加上 $a$，得到： $$t \equiv 2t \pmod b$$

两边同时减去 $t$，得到： $$0 \equiv t \pmod b$$

这意味着，只要步数 $t$ 是环长 $b$ 的整数倍，且两个指针都已进入环中，它们就一定会相遇。

4. 证明 $t$ 的存在性

为了让两指针在环内相遇，步数 $t$ 必须满足两个条件： 1. $t \ge a$ （确保慢指针已进入环内） 2. $t = k \cdot b$ （其中 $k$ 为正整数，确保满足相遇条件）

因此，我们只需要找到一个正整数 $k$，使得： $$k \cdot b \ge a \implies k \ge \frac{a}{b}$$

因为 $a$ 和 $b$ 都是有限的常数，我们显然可以找到满足该不等式的最小正整数 $k = \lceil \frac{a}{b} \rceil$（若 $a=0$，则取 $k=1$）。

此时对应的步数 $t = \lceil \frac{a}{b} \rceil \cdot b$ 是一个有限的确定值。这证明了快慢指针在有限步数内必然会相遇。

二、 实例分析

为了更直观地理解，我们来看一个具体的例子。

示例参数：

• 起点到环入口的距离 $a = 3$（节点 1 $\to$ 2 $\to$ 3 $\to$ 4，其中 4 是入口）
• 环的长度 $b = 4$（环为 4 $\to$ 5 $\to$ 6 $\to$ 7 $\to$ 4）
• 整个链表结构：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> (回到4)

根据之前的数学公式，预测相遇的步数 $t$ 为： $$t = \lceil \frac{3}{4} \rceil \cdot 4 = 1 \cdot 4 = 4$$

逐步追踪指针位置：

从表格中可以看出，在第 4 步时，两个指针在节点 5 处相遇，这与数学推导完全一致。

三、 C++11 代码实现

下面是使用 C++11 实现的标准检测链表是否有环的代码：

#include <iostream>

// 定义链表节点结构
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool hasCycle(ListNode* head) {
        // 如果链表为空或只有一个节点，显然无环
        if (head == nullptr || head->next == nullptr) {
            return false;
        }

        ListNode* slow = head;
        ListNode* fast = head;

        // 快指针每次走两步，慢指针每次走一步
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;

            // 如果相遇，说明有环
            if (slow == fast) {
                return true;
            }
        }

        // 如果快指针指向了 nullptr，说明链表有终点，无环
        return false;
    }
};

// 测试辅助函数：销毁有环链表以防内存泄漏（实际应用中需小心处理）
void freeCycleList(ListNode* head, int a) {
    ListNode* curr = head;
    ListNode* entry = nullptr;
    int count = 0;
    while (curr != nullptr) {
        if (count == a) {
            entry = curr;
        }
        ListNode* nextNode = curr->next;
        // 如果遇到了环的连接点，断开环并释放后续内存
        if (nextNode == entry && count > a) {
            curr->next = nullptr;
        }
        curr = nextNode;
        count++;
    }

    // 释放断开后的单链表
    curr = head;
    while (curr != nullptr) {
        ListNode* temp = curr;
        curr = curr->next;
        delete temp;
    }
}

int main() {
    // 构建示例中的链表: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 4
    ListNode* n1 = new ListNode(1);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(3);
    ListNode* n4 = new ListNode(4);
    ListNode* n5 = new ListNode(5);
    ListNode* n6 = new ListNode(6);
    ListNode* n7 = new ListNode(7);

    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
    n5->next = n6;
    n6->next = n7;
    n7->next = n4; // 创造环

    Solution solution;
    if (solution.hasCycle(n1)) {
        std::cout << "链表中存在环。" << std::endl;
    } else {
        std::cout << "链表中不存在环。" << std::endl;
    }

    // 清理内存
    freeCycleList(n1, 3);

    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com