快慢指针寻找链表环就快指针速度的疑问
来源：1-4 如何回答算法面试问题
甲骨文_0001
2021-11-04
老师，在一个链表中，两个指针同时同地出发，慢指针每次移动一步，快指针每次移动2步，当快指针下次碰到慢指针的时候说明链表存在环，能理解。就是快指针每次移动2步，那快指针每次移动3步，或4，5步可以吗 能够发生快指针后面会碰上慢指针的情况吗：）
写回答
1回答
-
liuyubobobo
2021-11-05
是的，快指针移动任意步都会碰到。
证明稍微有些复杂，需要一定的数论知识了，你要是有兴趣，在研究明白为什么快指针的速度是 2 的情况下，能相遇，在这个基础上，可以尝试证明把 2 修改成任意 k。
但是，快指针的移动次数是 2，首先模拟起来更简单，其次，他们相遇的时间会更短。
（最差的时间复杂度肯定是 O(n)的，n 是链表中的节点个数。但如果快指针速度很大，很有可能在环中兜非常多的圈。可以用极限思维去想，如果快指针的速度是 v = 10000000，此时，快指针的速度成为了算法性能的主导向，而非链表中的节点个数。在最差情况下，将按照这个速度，对环中的每一个点都遍历一遍，复杂度成为了 O(vn)。这不是严格证明，但可以直观看到可能的结果。）
继续加油！：)
112021-11-05
相似问题