热门标签
热门文章
- 1掌握Python图像处理艺术：Pillow库入门实践与案例解析_pillow库 python 案例
- 2Git 使用 SSH 密钥身份验证_git验证ssh
- 3WPF基础四：UI相关的类 (1) 父类_wpf 调用suspendlayout暂停布局
- 4AI与音乐：共创未来还是艺术终结？
- 5利用Python进行数据分析_python 进行data analysis
- 6sort 排序_sort(a, a + (n + n - m));
- 7Hive on Spark、Spark on Hive的异同_hiveonspark和sparkonhive区别
- 8javax.xml.transform.sax_javax.xml.transform.sax.saxtransform
- 9构建vue大项目报错：Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memo_<--- js stacktrace ---> fatal error: ineffective m
- 10selenium 效率优化_selenium cpu占用高
当前位置: article > 正文
快慢指针判断链表是否有环以及找环的入口_快慢指针判断环入口
作者：秋刀鱼在做梦 | 2024-07-28 18:19:55
赞
踩
快慢指针判断环入口
一，定义
快指针fast每次走两步，慢指针slow每次走一步
%表示取模运算
二，判断是否有环
刚开始时fast和slow都在链表头；
- 如果链表无环，那fast和slow指针不可能相遇，且最终fast=null
- 如果链表有环，记开始位置到环入口长度为k，环长为R，那么t时刻(t>=k)，fast在环上(2t-k)%R的位置，slow在环上(t-k)%R的位置，当(2t-k)%R=(t-k)%R时，t=n*R，所以快慢指针一定相遇，相遇点在(-k)%R
三，寻找环入口
快慢指针相遇时，它们都在(-k)%R处；
让快指针从头开始一步一步走，慢指针也走，那么当快指针走到环入口时，慢指针走到了
((-k)%R+k)%R=(-k)%R%R+k%R=(-k)%R+k%R=0%R=0处，此时快慢指针再次相
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/895296
推荐阅读
相关标签
