Floyd 循环检测算法(快慢指针法/龟兔指针法)
2024-09-07 22:40:11
Floyd Cycle Detection Algorithm
Floyd Cycle Detection Algorithm,即 Floyd 循环检测算法,又称快慢指针法、龟兔指针法。该算法用于判断链表是否存在环,以及判断环的起点与长度的算法。
算法原理
该算法基于两个指针,从头开始遍历,一个指针跑得快,另一个指针跑得慢,其中快指针的速度是慢指针的2倍。只要存在环,无论快慢指针从哪里开始,那么快慢指针最终一定会相遇,因为快指针没走一次,都会向慢指针靠近一个节点。
算法应用
判断是否有环
如果存在环,快慢指针必定相遇,反之,如果慢指针走到结尾还没相遇则不存在环。
求环的长度
假设存在环,那么快慢指针必定相遇,假设快慢指针在 X 点第一次相遇,此时再让两指针前进,下次相遇时快指针比慢指针多走了一圈,由此即可计算出环长度。
求环的起点
当快慢指针第一次相遇后,将慢指针指向头节点,快指针指向相遇点的下一个节点。再次让快慢指针运动,当快慢指针再次相遇时,相遇点即为环的第一个节点。
最新文章
- nodejs 代理 解决开发环境跨域问题
- 如何查看当前使用的Entity Framework版本
- sqlserver 2008 数据库表结构脚本及数据导出
- [PHP]array_map与array_column之间的关系
- FPGA最小系统分析与电路设计
- 第八章 标准IO库
- qt实现头像上传功能(写了4个类,朝十晚八的博客,非常好)
- ##DAY5 UIControl及其子类
- poj 1256 Anagram(dfs)
- Struts2-ActionContext
- [CF337D]邪恶古籍-树状dp
- JDBC中rs.beforeFirst()
- 【6】-BAT面试之操作系统内存详解
- Appium+python 使用 press_keycode 如何输入大写字母
- springboot10-springcloud-eureka 服务注册与发现,负载均衡客户端(ribbon,feign)调用
- 下载完整版Chrome离线安装文件的官方地址
- Add map surrounds using the SymbologyControl
- 前端开发中常用的CSS选择器解析(一)
- C#-语言基础+数据类型+运算符
- equals()重写
热门文章
- 【LeetCode】260. Single Number III 解题报告(Python & C++)
- 『学了就忘』vim编辑器基础 — 95、命令模式中的相关命令
- MacOS使用Docker创建MySQL主主数据库
- 使用子查询获取,使用 all 关键字获取比所有“国内短线游”价格高的线路信息,按照线路类型、线路价格升序显示线路编号、线路名和价格
- 你在寻找Vue3移动端项目框架嘛?请看这里
- SpringBoot集成Actuator监控管理
- C#读取注释的方法
- java 封装 总结
- Word2010制作倒福字
- Allwinner F1C100s coremark测试