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

弗洛伊德判圈算法核心是用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  # 弗洛伊德  # 链表  # 小环  # 跳过  # 的是  # 就会  # 放在  # 尤其是  # 最多  # 走到 

相关栏目： 【 Google疑问12 】 【 Facebook疑问10 】 【 网络优化76771 】 【 技术知识130152 】 【 IDC云计算60162 】 【 营销推广131313 】 【 AI优化88182 】 【 百度推广37138 】 【 网站推荐60173 】 【 精选阅读31334 】

相关推荐： Mac如何设置动态壁纸？（让桌面动起来）  使用类变量定义字符串常量时的类型安全最佳实践  如何高效获取循环末次生成的 NumPy 数组最后一个元素（无需额外循环）  如何在Golang中定义接口_抽象方法和多态实现  Win11怎么设置麦克风权限_允许应用访问Win11麦克风【详解】  Windows系统被恶意软件破坏后的恢复策略_错误提示修复方式  网站体验不好=浪费钱:如何提升-用户体验效果差  如何使用Golang配置安全开发环境_防止敏感信息泄露  php订单日志怎么记录发货_php记录订单发货操作日志指南【指南】  Win10系统更新错误0x80240034怎么办 Win10更新错误解决法【方法】  Mac的访达（Finder）怎么用_Mac文件管理入门教程【详解】  Win11怎么设置组合键快捷方式_Windows11自定义快捷键操作  如何使用Golang实现容器健康检查_监控和自动重启  Windows怎样关闭桌面弹窗广告_Windows关闭桌面弹窗设置【教程】  为什么本地php环境运行php脚本卡顿_php执行效率优化方法与设置【说明】  如何使用Golang实现多重错误处理_Golangerror组合与判断方法  Python正则表达式实战_模式匹配说明【教程】  如何在Golang中使用log包输出不同级别日志_Golang log日志管理与分类  如何在Golang中实现WebSocket广播_使用Channel和协程分发消息  如何在Golang中编写端到端测试_Golang E2E测试流程示例  c++中如何对数组进行排序_c++数组排序算法汇总  c++的static关键字有什么用 静态变量和静态函数的应用场景【教程】  C++中的constexpr和const有什么区别？（编译期常量）  Mac怎么设置登录项_Mac管理开机自启动程序【教程】  Python音视频处理高级项目教程_FFmpegPydub剪辑与特效  Python并发安全问题_资源竞争说明【指导】  c++中如何使用auto关键字_c++11类型推导用法说明  Win11怎么设置虚拟内存最佳大小_Windows11性能选项自定义分页文件  PythonFastAPI项目实战教程_API接口与异步处理实践  MAC怎么用连续互通相机里的“桌上视角”_MAC在视频通话中同时展示人脸和桌面  Win11任务栏怎么固定应用 Win11将软件图标固定到底部【步骤】  如何在Golang中实现微服务负载均衡_Golang负载均衡策略与实现示例  如何在 Go 应用中实现自动错误恢复与进程重启机制  Win10怎样安装Word样式库_Win10安装Word样式教程【步骤】  XAMPP 启动失败（Apache 突然停止）的终极排查与修复指南  php怎么连接数据库_MySQL数据库连接的基础代码编写【说明】  Win11怎样激活系统密钥_Win11系统密钥激活步骤【攻略】  Win11怎么设置开机问候语_自定义Win11锁屏提示信息【技巧】  windows如何备份注册表_windows导出和导入注册表文件教程  Win11怎么清理C盘系统错误报告_Win11清理系统错误报告技巧【教程】  Win11如何关闭小娜Cortana Win11禁用Cortana语音助手【优化】  Win11关机界面怎么改_Win11自定义关机画面设置【工具】  Windows服务启动类型恢复方法_错误修改导致的系统服务异常  Windows10如何彻底关闭自动更新_Win10服务与组策略双重禁用  MAC的“接续互通”功能无法使用怎么办_MAC检查蓝牙、Wi-Fi和相同Apple ID登录  Win11怎么连接投影仪_Win11多显示器投屏设置指南【步骤】  如何优化Golang Web性能_Golang HTTP服务器性能提升方法  Mac系统更新下载慢或失败怎么办_解决macOS升级问题【方法】  Python文件和流处理指南_高效读写大体积数据文件  windows如何修改文件默认打开方式_windows设置程序关联教程 

 2026-01-05