c++中如何实现弗洛伊德判圈算法_c++判断链表是否有环_网络技术

c++中如何实现弗洛伊德判圈算法_c++判断链表是否有环

发布时间 - 2026-01-05 00:00:00 点击率：次

弗洛伊德判圈算法核心是用slow（步长1）和fast（步长2）双指针遍历单链表，若相遇则有环，若fast遇nullptr则无环；C++实现需先判空和单节点，循环条件为fast&&fast->next，移动后立即比较指针是否相等。

弗洛伊德判圈算法的核心逻辑是什么

它不依赖额外空间，只用两个指针——slow 和 fast，在单链表上同步移动：slow 每次走 1 步，fast 每次走 2 步。如果链表有环，二者必在环内相遇；若 fast 先走到 nullptr，说明无环。

如何用 C++ 实现基础判环（无环返回 false，有环返回 true）

注意边界：空链表或仅一个节点时，fast->next 可能非法，必须先检查 fast 和 fast->next 是否为 nullptr。

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

为什么 fast 要走两步而不是三步或更多

走两步是效率与正确性平衡的结果：

若 fast 走 3 步，可能跳过 slow，导致一次循环内不相遇，需更多轮才能捕获，但不破坏正确性
但走 2 步能保证：只要存在环，相对速度为 1，fast 必然在有限步内追上 slow（数学上可证最多绕环一圈就相遇）
走 >2 步会增加空指针解引用风险（如 fast->next->next->next），且无性能收益

常见误写和崩溃点

最常出错的是循环条件和移动顺序：

错误写法：while (fast->next && fast) —— 顺序反了，fast 为 nullptr 时访问 fast->next 直接段错误
错误写法：先移动再判断（如把 if (slow == fast) 放在移动之后但没处理初始重合）—— 若链表只有一个节点且自环（head->next == head），初始 slow == fast，但未进循环就被跳过
正确做法：循环条件严格为 fast && fast->next，且每次移动后立即判断相等

环检测本身不难，但指针操作的边界稍一松懈就会 crash，尤其是和 LeetCode 测试用例里各种极端结构（空、单节点、自环、长链+小环）打交道时，条件顺序和判空缺一不可。

# node # c++ # 为什么 # if # while # 循环 # 指针 # 空指针 # 算法 # leetcode # 弗洛伊德 # 链表 # 小环 # 跳过 # 的是 # 就会 # 放在 # 尤其是 # 最多 # 走到

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：《不朽箴言》T0最强阵容搭配推荐

下一篇：百度云盘下载太慢怎么办_百度网盘下载慢原因及解决方法

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：《不朽箴言》T0最强阵容搭配推荐

下一篇：百度云盘下载太慢怎么办_百度网盘下载慢原因及解决方法