算法详解：如何判断链表中是否存在环（C++实现）

算法详解：如何判断链表中是否存在环（C++实现）

引用

CSDN

1.

https://m.blog.csdn.net/Vitalia/article/details/146176116

141. Linked List Cycle

给定链表的头节点 head，判断链表中是否存在环。如果链表中存在环，则返回 true；否则返回 false。

链表中存在环的条件是：链表中某个节点的 next 指针可以指向链表中的任意节点，从而形成一个闭环。内部使用 pos 来表示尾节点的 next 指针连接到的节点的索引位置。需要注意的是，pos 不作为函数参数传递。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中存在环，尾节点的 next 指针指向了链表中的第 1 个节点（0 索引）。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中存在环，尾节点的 next 指针指向了链表中的第 0 个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中不存在环。

问题描述

给定一个链表的头节点 head，判断链表中是否存在环。如果链表中存在环，则返回 true；否则返回 false。

解题思路

判断链表是否有环的经典方法是使用 快慢指针（Floyd’s Cycle Detection Algorithm），也称为龟兔赛跑算法。其核心思想是：

• 使用两个指针，一个快指针（每次走两步）和一个慢指针（每次走一步）。
• 如果链表中存在环，快指针最终会追上慢指针。
• 如果链表中不存在环，快指针会到达链表的末尾（nullptr）。

C++ 代码实现

// 链表节点定义
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; // 快指针到达链表末尾，说明无环
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是链表的节点数。
• 如果链表无环，快指针会遍历链表一次。
• 如果链表有环，快慢指针会在环内相遇，时间复杂度仍为 $O(n)$。
• 空间复杂度：$O(1)$，只使用了常数级别的额外空间。

总结

通过快慢指针法，我们可以高效地判断链表是否有环。这种方法不仅代码简洁，而且性能优秀，适合处理大规模数据。掌握快慢指针的思想对于解决类似的链表问题非常有帮助。