c++中如何使用快慢指针判断链表环_c++快慢指针判断环方法-C++-PHP中文网

c++中如何使用快慢指针判断链表环_c++快慢指针判断环方法

裘德小鎮的故事

发布： 2025-10-11 14:52:01

原创

207人浏览过

快慢指针法通过设置每次移动1步的慢指针和2步的快指针，从头节点出发遍历链表，若存在环则二者必相遇，否则快指针会到达末尾；C++实现中需判断fast及fast->next非空，时间复杂度O(n)，空间复杂度O(1)。

c++中如何使用快慢指针判断链表环_c++快慢指针判断环方法

在C++中，使用快慢指针（也叫Floyd判圈法）判断链表是否存在环是一种高效且常用的方法。其核心思想是利用两个移动速度不同的指针遍历链表，如果链表中存在环，快慢指针最终会相遇。

快慢指针基本原理

定义两个指针：

慢指针（slow）：每次向前移动1步。
快指针（fast）：每次向前移动2步。

从头节点出发，如果链表无环，快指针会先到达末尾（nullptr）；如果有环，快指针会在环内循环，而慢指针也会进入环，由于速度快，最终会追上慢指针。

C++实现代码示例

#include <iostream>
using namespace std;

// 链表节点定义
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 != nullptr && fast->next != nullptr) {
        slow = slow->next;          // 慢指针走一步
        fast = fast->next->next;   // 快指针走两步

        if (slow == fast) {          // 指针相遇，说明有环
            return true;
        }
    }
    return false; // 快指针到尾部，无环
}

登录后复制