C语言单向环形链表：检测环与入口点算法详解

追风的人

发布时间：2026-10-13 | 5人浏览过

原创

面对单向链表是否带环以及寻找环入口的经典问题，仅靠直观观察难以给出严谨结论。本文将利用快慢指针（Floyd判圈算法）的核心思想，从检测环的存在性出发，逐步推导到精确定位入口点的数学原理。通过图解与代码结合的方式，解析slow与fast在不同步长下的追及逻辑，并提供可直接使用的C/C++代码实现，解决数据结构中的这一难点。

1. 环形链表基础与题目引入

在标准单链表中，每个节点指向下一个节点，最后一个节点的指针域为空（NULL）。但在某些场景下，链表可能形成闭环，即最后一个节点不再指向空，而是指向链表中间某个节点，从而形成环形链表。

正常单链表结构如下，尾部终止：

而带有环的链表，尾部节点重新指向头部或中间节点，导致遍历进入死循环：

2. 检测环的存在：快慢指针法

要判断链表是否有环，最经典且高效的方法是使用“快慢指针”。其核心思路是将抽象的直线段与圆环段分开看待：在进入环之前，两指针同向而行；进入环后，由于速度差，快指针最终会追上慢指针。

第1步：初始化双指针

定义两个指针 slow 和 fast，均指向链表的头节点 head。slow 每次前进1步，fast 每次前进2步。

第2步：执行追赶逻辑

在循环中移动指针：slow = slow->next，fast = fast->next->next。如果 fast 或 fast->next 为 NULL，说明链表无环，直接返回 false。

关键现象：当 slow 走到直线一半位置时，fast 通常已经入环并开始追赶。一旦 slow 也进入环内，fast 便开始缩短与 slow 的距离。

当 slow == fast 时，说明两者相遇，链表必然存在环。以下是检测环存在的完整代码：

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            return true; // 相遇，有环
        }
    }
    return false; // 到达末尾，无环
}

3. 深度拓展：步长变化的影响

虽然 "1步 vs 2步" 是标准解法，但理解不同步长的追及逻辑有助于更深入掌握算法本质。

（1）为什么 1步和 2步一定能追上？

当 slow 进入环时，fast 已经在环内。假设此时两者距离为 N。

slow 走1步，fast 走2步。
每经过一次迭代，fast 相对 slow 前进一步，距离缩小1（变为 N-1）。
以此类推，距离最终会缩减至0，即追上。

（2）如果 fast 走3步或4步呢？

答案：不一定能追上。

以 1步 vs 3步为例：每轮迭代距离缩短2。若初始距离 N 为奇数，则距离会变成 N-2, ..., 1, -1（此时相当于错开一圈，距离变为环长 C-1）。如果 C-1 仍为奇数，则永远无法缩小到0，陷入无限循环。

4. 如何找到环的入口点？

检测到环后，接下来的目标是定位入环口。这可以通过数学公式严格推导得出。

第1步：建立数学模型

设：

L：链表头到入环口的距离。
X：入环口到首次相遇点的距离。
C：环的长度。
N：快指针在环内多跑的圈数（N >= 0）。

在相遇时：

慢指针路程：S_slow = L + X
快指针路程：S_fast = L + N*C + X

因为快指针速度是慢指针的2倍（在相同时间内），所以：

2 * (L + X) = L + N*C + X

化简该式：

2L + 2X = L + NX + XC

L + X = N*C

L = N*C - X

或者写成：L = (N-1)*C + (C - X)

第2步：推导入口定位逻辑

根据公式 L = N*C - X（假设 N>=1，若N=0则L=C-X同样成立逻辑），我们可以得出一个极具实用价值的结论：

如果从一个指针从头节点出发，另一个指针从相遇点出发，且都保持每次1步的速度，它们最终会在入环口相遇。

原理解释：
从相遇点再走 C-X 的距离即可回到入环口。而公式表明，从头节点走 L 的距离，正好等于在环内绕 (N-1) 圈后再走 C-X 的距离。因此，两条路径长度等效。

第3步：代码实现查找入口

基于上述逻辑，我们可以在检测到 slow == fast 后，将其中一个指针重置到头节点，继续同步移动，直到再次相遇。

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    // 第一阶段：检测是否有环
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast)
        {
            // 第二阶段：寻找入口点
            struct ListNode* meet = slow;
            // 将一个指针放回head，另一个保持meet，同速前进
            while (meet != head)
            {
                meet = meet->next;
                head = head->next;
            }
            return meet; // 相遇点即为入口
        }
    }
    return NULL; // 无环
}