C++判断链表是否有环并找到入口结点的算法详解

程一诺

发布时间：2026-10-16| 6人浏览过

原创

在C++面试及算法练习中，如何高效地找出链表的环入口结点是一个经典考点。本文详细解析了满足O(1)空间复杂度的快慢指针算法及其数学原理，同时提供基于哈希表的辅助解法。

问题描述与约束

给定一个长度为 $n$ 的链表，若其中包含环，请找出该环的入口结点；若不存在环，则返回 null。

数据范围：$n \le 10000$，结点值介于 1 到 10000 之间。
核心要求：时间复杂度需为 O(n)，空间复杂度必须控制在 O(1)（即不能使用额外的哈希集合或数组）。
输入说明：链表分为入环前部分和环内部分，例如输入 {1,2} 和 {3,4,5} 时，实际构成的环形结构如下图所示：
如上图中，入口结点值为 3，程序应返回指向该结点的指针，后台将打印对应的结点值。

解题思路

针对此题，主要有两种常见的解决路径。第一种是利用哈希表记录访问过的节点，但受限于空间复杂度 O(1) 的要求，通常不作为最优解，这里仅作对比说明。第二种是经典的「快慢双指针法」，这是本题的标准答案。

解法一：哈希 Set（空间复杂度 O(n)）

虽然不符合最严格的 O(1) 空间要求，但该逻辑最直观。使用 std::unordered_set 存储遍历过的指针地址。每当遇到新节点时检查是否已存在于集合中：

若不存在，将其插入集合并继续向下遍历。
若发现该指针已在集合中，说明当前节点即为环的入口结点。

解法二：快慢双指针（推荐，空间复杂度 O(1)）

这是本题的核心解法，其正确性基于以下数学推导过程：

定义变量：设头节点 A 到环入口 B 的距离为 $X$，环入口 B 到第一次相遇点 C 的距离为 $Y$，环 C 到 B 的剩余距离为 $Z$。环周长即为 $Y+Z$。
第一次相遇：当快慢指针在 C 点相遇时，慢指针走了 $X+Y$。因为快指针速度是慢指针的 2 倍，所以快指针走了 $2(X+Y)$。此时快指针不仅在链表中走了一次 X+Y，还在环里多走了若干圈。
距离关系：快指针比慢指针多走的距离一定是环周长的整数倍，即：$2(X+Y) - (X+Y) = Y+Z = k(Y+Z)$。推导出 $X = (k-1)(Y+Z) + Z$。这意味着，从起点 A 走 X 步到达入口 B 的距离，等同于从相遇点 C 走 Z 步再绕环一圈的距离。
确定入口：既然 $A \rightarrow B$ 的距离等于 $C \rightarrow B$ 加上环长，我们可以将其中一个指针重置回头节点 A，让两个指针以相同的速度（每次一步）前进。当它们再次相遇时，正好就是环入口 B。

C++ 实现代码

1. 哈希 Set 实现

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        std::unordered_set<ListNode*> S;
        while(pHead != nullptr)
        {
            // 如果节点已经存在，说明找到了环入口
            if(S.find(pHead) != S.end()) 
            {
                return pHead;
            }
            // 否则存入集合并移动指针
            S.insert(pHead);
            pHead = pHead->next;
        }
        return nullptr;
    }
};

2. 快慢双指针实现（O(1) 空间）

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        // 边界情况：空链表无环
        if(pHead == nullptr || pHead->next == nullptr) 
            return nullptr;
        
        // 初始化快慢指针
        ListNode* slow = pHead;
        ListNode* fast = pHead;
        
        // 第一阶段：寻找相遇点
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;           // 慢指针走 1 步
            fast = fast->next->next;     // 快指针走 2 步
            
            // 如果相遇，说明有环
            if(slow == fast) 
                break;
        }
        
        // 若 fast 为空，说明未形成闭环
        if(fast == nullptr || fast->next == nullptr)
            return nullptr;
        
        // 第二阶段：寻找入口点
        // 将快指针重置到头部，两者同速前进
        fast = pHead;
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        
        // 相遇点即为环入口
        return fast;
    }
};