如何利用快慢指针算法秒级检测一个未知链表中是否存在死圈

胖婷酱_2810

胖婷酱_2810

2026-06-04

714人浏览

原创

快慢指针算法可在o(n)时间、o(1)空间内检测链表环,需严格初始化双指针于head、先空检查再移动、循环中先移后判且fast必须完整走两步,相对速度为1保证必相遇,常见错误是空指针未检、提前比较、循环条件不全。

如何利用快慢指针算法秒级检测一个未知链表中是否存在死圈

快慢指针算法能在O(n)时间、O(1)空间内完成检测,无需遍历两次,也无需哈希表——真正实现“秒级”判断。关键不在速度多快,而在于逻辑简洁、边界清晰、一次到位。

初始化必须严格规范

两个指针都从 head 节点出发(不是 head->next),且必须先做空检查:

  • 若 head == nullptr 或 head->next == nullptr,直接返回 false
  • 否则令 slow = head,fast = head

移动与判断顺序不能颠倒

循环中必须先移动、后比较,且 fast 的移动要完整执行两步:

Happy Oyster
Happy Oyster

一款AI开发辅助工具,主要用于阿里巴巴推出的实时交互式3D世界模型,适合需要提升相关任务效率的用户。

下载
  • 每次循环:slow 走 1 步 → fast 走 2 步(即 fast = fast->next->next)
  • 移动完成后,再判断 slow == fast
  • 循环条件是 fast != nullptr && fast->next != nullptr,缺一不可,否则会解引用空指针

为什么一定能相遇?不是靠运气

只要存在环,快慢指针必然相遇,原因在于相对速度恒为 1:

  • 快指针每轮比慢指针多走 1 个节点,相当于以“1 节点/轮”的速度追赶
  • 设二者进入环时距离为 d(d ≥ 1),最多 d 轮后必重合
  • 若快指针走 3 步、慢指针走 1 步,相对速度为 2,可能因环长和初始距离奇偶性错失相遇

常见误判点就这三处

90% 的错误来自以下任一疏忽:

  • 没检查 head 或 head->next 是否为空,导致单节点链表误判为有环
  • 在移动前就比较 slow == fast,头节点就相等,直接返回 true
  • while 条件只写 fast != nullptr,漏掉 fast->next != nullptr,访问非法内存

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

5716

4

Linux 新手先学哪些命令
Linux 新手先学哪些命令

Linux新手命令专题汇集终端基础、文件目录操作、文本查看、软件安装和权限管理等入门文章,帮助按实际任务练习常用命令并建立命令行操作习惯。

2026.10.15

0

20

MySQL 忘记密码怎么办
MySQL 忘记密码怎么办

MySQL忘记密码专题汇集不同版本与系统下的root密码重置方法,覆盖MySQL 5.7、8.0、Mac、Linux及本地集成环境,并提示恢复权限与重新登录的检查步骤。

2026.10.15

0

18

Vue.js 中 ref 和 reactive 的区别
Vue.js 中 ref 和 reactive 的区别

Vue.js中ref和reactive的区别专题汇集两种响应式API的定义、访问方式、对象解构、侦听与性能取舍等文章,帮助结合实际状态类型选择合适写法。

2026.10.15

0

20

VS Code 怎么配置开发环境
VS Code 怎么配置开发环境

VS Code开发环境专题汇集编辑器安装、语言扩展、编译器、解释器、终端和调试配置文章,覆盖Java、Python、C++和PHP等常见语言的入门设置。

2026.10.15

0

18

C++ 开发环境怎么搭建
C++ 开发环境怎么搭建

C++开发环境专题汇集Windows、Linux下的编译器与IDE安装配置教程,涵盖GCC、Clang、Visual Studio、CLion和VS Code,以及编译运行首个程序的步骤。

2026.10.15

0

19

Python 虚拟环境是什么
Python 虚拟环境是什么

Python虚拟环境专题介绍项目依赖隔离的作用,汇集venv与uv创建、激活、退出及解释器切换的相关文章,并覆盖Windows、Linux和VS Code中的常见配置问题。

2026.10.15

0

15

Python 怎么安装并配置环境变量
Python 怎么安装并配置环境变量

Python安装与环境变量配置专题汇集Windows、macOS和Linux的安装步骤、PATH设置、pip配置及常见报错排查文章,帮助完成解释器安装并验证命令行可以正常运行。

2026.10.15

0

15

PHP 连接 MySQL 失败怎么办
PHP 连接 MySQL 失败怎么办

PHP连接MySQL失败专题汇集PDO与MySQLi扩展配置、账号权限、主机端口、套接字和认证方式等排查文章,覆盖连接报错、密码变更与容器环境配置,帮助按错误提示定位原因并修复。

2026.10.15

0

18

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
深入剖析redis教程
深入剖析redis教程

共55课时 | 9.8万人学习

麦子学院深入浅出 redis 视频教程
麦子学院深入浅出 redis 视频教程

共20课时 | 5.1万人学习

传智播客redis基础视频教程
传智播客redis基础视频教程

共13课时 | 6.1万人学习