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 】

相关推荐： Win11怎么制作U盘启动盘_Win11原版系统安装盘制作【详解】  MySQL 中使用 IF 和 CASE 实现查询字段的条件映射  如何使用Golang管理跨项目依赖_Golang多模块项目依赖实践  如何使用Golang实现容器健康检查_监控和自动重启  Win10 BitLocker加密教程 Win10给磁盘驱动器上锁【安全】  Win11怎么清理C盘下载文件夹_Win11清理下载文件夹技巧【教程】  C#如何在一个XML文件中查找并替换文本内容  Windows10电脑怎么设置虚拟内存_Win10高级系统设置性能  Windows10怎样设置家长控制_Windows10家长控制设置方法【指南】  短链接怎么用php递归还原_多层加密链接的处理法【详解】  Windows10如何查看保存的WiFi密码_Win10命令行netsh wlan查询  c++如何判断文件是否存在_c++ filesystem库用法  c++怎么处理多线程死锁_c++ lock_guard与unique_lock锁管理【技巧】  Win11输入法选字框不见了怎么办_Win11输入法修复与重置【教程】  Win10怎样设置多显示器_Win10多显示器扩展设置【攻略】  Windows10电脑怎么设置电源按钮_Win10按电源键关机或休眠  php中$this和::能混用吗_对象与静态作用域冲突解决【方法】  如何使用Golang recover捕获panic_防止程序崩溃并处理异常  c++ unordered_map怎么用 c++哈希表用法【教程】  如何使用正则表达式批量替换重复的“-”模式为固定字符串  Mac如何开启夜览模式_Mac护眼模式设置与定时  c++ stringstream用法详解_c++字符串与数字转换利器  MAC怎么截图并快速编辑_MAC自带截图快捷键与标注工具使用【方法】  Drupal 中 HTML 链接被重复转义导致渲染异常的解决方案  php命令行怎么运行_通过CLI模式执行PHP脚本的步骤【说明】  Mac如何彻底清理浏览器缓存？（Safari与Chrome）  PHP主流架构如何处理会话管理_Session与Cookie【技巧】  MySQL 中使用 IF 和 CASE 实现查询字段条件化显示  Mac电脑如何恢复出厂设置_Mac抹掉数据并重装系统【安全指南】  Win11此电脑不在桌面上_Windows 11桌面图标设置找回【步骤】  Win11怎么设置虚拟内存_Windows 11优化内存性能提升速度【技巧】  Win11怎么设置默认视频播放器_Windows 11关联媒体文件打开方式【步骤】  C++中的std::shared_from_this有什么用？C++安全获取this的shared_ptr【智能指针】  Python实现图数据库操作_Neo4j核心CRUD与图算法解析  Windows蓝屏错误0x0000002C怎么解决_系统IO异常排查方法  如何使用Golang模拟请求超时_Golang context与HTTP请求测试实践  Win11怎么设置默认邮件应用_Windows11应用关联Mail设置  Win11输入法切换快捷键怎么改_Windows 11自定义语言切换键位【教程】  Win10任务栏天气和资讯怎么关闭 Win10禁用新闻和兴趣功能【教程】  c++如何利用doxygen生成开发文档_c++ 代码注释规范与HTML文档导出【案例】  Win11如何关闭小娜Cortana Win11禁用Cortana语音助手【优化】  如何在 Go 项目开发中正确处理本地包导入与远程模块路径的一致性问题  如何在Golang中解压文件_Golang compress/gzip解压操作方法  如何在Golang中实现微服务负载均衡_Golang负载均衡策略与实现示例  php订单日志怎么按状态筛选_php筛选不同状态订单日志教程【教程】  如何用列表一次性对 DataFrame 的指定列应用字典映射  Win11玩游戏全屏闪退怎么办_Win11全屏优化禁用设置【教程】  Win11文件夹预览图不显示怎么办_Win11缩略图缓存重建修复【教程】  如何在 VS Code 中正确配置并使用 NumPy  Python文件和流处理指南_高效读写大体积数据文件 

 2026-01-05