c++中如何判断链表环_c++链表环判断方法-C++-PHP中文网

c++中如何判断链表环_c++链表环判断方法

冰火之心

发布： 2025-09-28 18:09:01

原创

433人浏览过

使用快慢指针法可高效判断链表是否存在环，时间复杂度O(n)，空间复杂度O(1)；通过快指针每次走两步、慢指针每次走一步，若相遇则有环，否则无环。

c++中如何判断链表环_c++链表环判断方法

在C++中判断链表是否存在环，最常用的方法是快慢指针法（也叫弗洛伊德判圈算法）。这种方法效率高，时间复杂度为O(n)，空间复杂度为O(1)。

快慢指针法原理

使用两个指针，一个慢指针（slow）每次移动一步，一个快指针（fast）每次移动两步。如果链表中存在环，快指针最终会追上慢指针；如果没有环，快指针会到达链表末尾。

关键逻辑：

初始化：slow 和 fast 都指向头节点
循环条件：fast 不为空，且 fast->next 不为空
slow = slow->next，fast = fast->next->next
如果 slow == fast，说明有环

C++实现代码

以下是完整的判断链表环的C++代码示例：

爱图表

AI驱动的智能化图表创作平台

查看详情

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

bool hasCycle(ListNode *head) {
    if (!head || !head->next) return false;

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

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return true;  // 存在环
        }
    }

    return false;  // 无环
}

登录后复制

如何找到环的入口（扩展）

如果不仅要判断是否有环，还要找到环的起始节点，可以在检测到环后继续处理：

立即学习“C++免费学习笔记（深入）”；

当 slow == fast 时，将 slow 重置回头节点
然后 slow 和 fast 都每次前进一步
它们相遇的位置就是环的入口

找环入口代码片段：

ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;

    // 先判断是否有环
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }

    if (!fast || !fast->next) return nullptr;  // 无环

    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;  // 返回环的入口
}

登录后复制

基本上就这些。快慢指针是解决链表环问题的标准做法，理解其运行机制后很容易应用。

以上就是c++++中如何判断链表环_c++链表环判断方法的详细内容，更多请关注php中文网其它相关文章！