c++怎么判断一个链表是否存在环_c++判断链表环的多种算法实现

下次还敢 2025-10-31 00:00:00 次阅读

答案：快慢指针法通过两个指针判断环，时间O(n)空间O(1)；哈希表法用set记录节点，时间O(n)空间O(n)；标记法修改节点标记，会破坏结构。推荐快慢指针法。

判断链表是否存在环是常见的数据结构问题。C++中可以通过多种方法解决，下面介绍三种常用且高效的实现方式：快慢指针法、哈希表法和标记法。

1. 快慢指针法（Floyd判圈算法）

这是最经典的方法，也叫“龟兔赛跑”算法。使用两个指针，一个每次走一步（慢指针），另一个每次走两步（快指针）。如果链表有环，它们最终会相遇；如果没有环，快指针会到达末尾。

优点：时间复杂度 O(n)，空间复杂度 O(1)。

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;
}

2. 哈希表法（使用set记录访问节点）

遍历链表，将每个节点的地址存入一个unordered_set中。如果发现当前节点已经在集合中，说明存在环。

优点：逻辑清晰，容易理解。
缺点：需要额外 O(n) 的空间。

#include 

bool hasCycle(ListNode *head) {
    std::unordered_set visited;
    while (head) {
        if (visited.find(head) != visited.end()) {
            return true;
        }
        visited.insert(head);
        head = head->next;
    }
    return false;
}

3. 标记法（修改节点值或指针）

利用题目限制较少的特点，可以给每个访问过的节点添加标记。例如将节点的 next 指向一个特殊地址（如头节点本身），或者修改 val 为特殊值（前提是允许修改原链表）。

注意：这种方法会破坏原始结构，不适用于只读场景。

bool hasCycle(ListNode *head) {
    while (head) {
        if (head->next == head) return true; // 已被标记
        ListNode *next = head->next;
        head->next = head; // 标记当前节点
        head = next;
    }
    return false;
}

基本上就这些。实际开发推荐使用快慢指针法，无需额外空间且不破坏链表结构，是最优解。面试中能写出这几种方案，体现对时间和空间权衡的理解。