链表是否有环快指针走三步_快指针每次跳三步是否能判断有环

作者：小蓝xlanll | 2024-02-06 20:42:47

踩

快指针每次跳三步是否能判断有环

百度三面问到的一个问题，判断链表是否有环
当时说的是快慢指针，快指针每次走两步
面试官后面说如果快指针走三步是不是一定会相遇
当时回答的不是很好，下面是我的想法，和大家交流一下

开始到出现环的位置长度为a
环的长度为b

慢指针入环的时候，快指针走过的长度为 3a，所以快指针在环上的位置是：(2a)%b
假设：慢指针走了x步之后两者相遇
此时快指针走过的长度为 3x
两者相遇的条件：(3x+(2a)%b)%b = x%b
即：3x+(2a)%b = x+nb (n=0……n)
x = (nb-(2a)%b) / 2
判断x为整数时，a和b要满足什么条件
如果b为偶数，(nb-(2a)%b) 也为偶数，所以会有整数解
如果b为奇数，(2a)%b 可能为奇数，也可能为偶数，同时nb也是奇偶不定，所以还是会相遇
结论：一定会相遇

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/64493

链表是否有环 快指针走三步_快指针每次跳三步是否能判断有环

链表是否有环快指针走三步_快指针每次跳三步是否能判断有环