C++怎么判断链表有环

在C++中判断链表是否存在环是数据结构领域的经典问题，链表有环指链表的某个节点的next指针指向了链表中之前出现的节点，最终形成闭环结构，常规的遍历计数或者标记节点的方法要么效率不高要么会修改原链表结构，而快慢指针法可以在不修改原链表、时间复杂度O(n)、空间复杂度O(1)的前提下完成检测。

快慢指针判断链表有环的原理

快慢指针的核心思路是定义两个指针，同时从链表的头节点出发，快指针每次向前移动两个节点，慢指针每次向前移动一个节点。如果链表不存在环，快指针会率先到达链表尾部，此时可以直接判定无环；如果链表存在环，快指针会在环内不断循环移动，最终一定会追上慢指针，也就是两个指针指向同一个节点，此时就可以判定链表存在环。

为什么快指针一定会追上慢指针？假设环的长度为L，当慢指针进入环时，快指针已经在环内的某个位置，两者的距离差最大为L-1，快指针每次比慢指针多走1个节点，最多经过L-1次移动，两者就会相遇，不可能出现快指针跳过慢指针的情况。

链表节点的定义

首先我们需要定义链表的基础节点结构，节点包含存储数据的成员和指向下一个节点的指针，示例代码如下：

// 定义链表节点结构
struct ListNode {
    int val;          // 节点存储的值
    ListNode* next;   // 指向下一个节点的指针
    // 构造函数，初始化节点值和next指针
    ListNode(int x) : val(x), next(nullptr) {}
};

快慢指针实现判断链表有环的完整代码

基于快慢指针的原理，我们可以实现判断函数，函数的入参是链表的头节点，返回值是布尔类型，true表示有环，false表示无环。

#include <iostream>
using namespace std;

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

/**
 * 判断链表是否存在环
 * @param head 链表头节点
 * @return 有环返回true，无环返回false
 */
bool hasCycle(ListNode* head) {
    // 链表为空或者只有一个节点且next为空，必然无环
    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;
        }
    }
    // 快指针到达尾部，说明无环
    return false;
}

// 测试代码
int main() {
    // 创建无环链表：1->2->3->4->null
    ListNode* head1 = new ListNode(1);
    head1->next = new ListNode(2);
    head1->next->next = new ListNode(3);
    head1->next->next->next = new ListNode(4);
    cout << "无环链表检测结果：" << (hasCycle(head1) ? "有环" : "无环") << endl;

    // 创建有环链表：1->2->3->4->2（尾节点指向第二个节点）
    ListNode* head2 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    head2->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2;  // 形成环
    cout << "有环链表检测结果：" << (hasCycle(head2) ? "有环" : "无环") << endl;

    // 释放无环链表内存，有环链表需要额外处理避免无限循环，这里简化测试省略
    delete head1->next->next->next;
    delete head1->next->next;
    delete head1->next;
    delete head1;
    return 0;
}

边界情况处理说明

在实现过程中需要注意几个边界情况，避免出现空指针访问的错误：

• 如果链表头节点为空，直接返回false，因为空链表不存在环。
• 如果链表只有一个节点，且next指针为空，返回false，单个节点无环。
• 快指针移动前需要判断fast->next是否为空，因为快指针要移动两步，如果fast->next为空，再访问fast->next->next就会出现空指针异常。
• 如果链表存在环，不要尝试遍历整个链表释放内存，否则会进入无限循环，需要额外记录访问过的节点再释放。

方法对比

除了快慢指针法，常见的判断链表有环的方法还有哈希表法和遍历标记法，三者的对比如下：

常见问题解答

快指针能不能每次走三步或者更多步？

理论上快指针每次走三步及以上也可以检测环，但是步数越大，出现空指针异常的概率越高，而且快指针可能会跳过慢指针，导致无法相遇，所以通常选择每次走两步是最稳妥的方案。

如果链表有环，快慢指针一定会在第一圈相遇吗？

不一定，相遇的位置取决于环的长度和慢指针进入环时快指针的位置，可能在慢指针走第一圈时相遇，也可能在走第二圈时相遇，但最多不会超过慢指针走两圈就会相遇。

C++链表有环判断快慢指针数据结构修改时间：2026-07-01 10:48:40