双指针快慢指针步数设置的问题

Question

老师，链表环的问题，一般都有快慢指针的解法，通常，快指针一次走2步，慢的一次走1步，双方都是从同一起点出发的，然后，后面某个时间点，快的会赶上慢的，也就是fastslow,指向一致了，说明有环，直观上也好懂。我的不解点是，为什么快fast一次设成走2步，能设成一次走3步，4步吗，如果这样，经过一段时间后，快的也赶上慢的，就是赶上了，能发生fastslow,因为很可能赶上那一刻，是 fast=slow+1这样的形式，还是说只有一个2步，一个1步，这样后面才可能fast==slow,望指点迷津:）

Answer 1

liuyubobobo 2019-06-26 10:50:49

需要具体问题具体分析。通常在具体问题中，是能证明出来为什么要设置两步。不排除一些奇怪的问题，快指针需要三步走四步五步走，这从来不是一个规则：）

最典型的例子，比如基于链表的归并排序，每次要找到链表的中间位置，一个简单的方法就是用快慢指针，快指针到头的时候，慢指针也就到中间了。此时快指针必须是两步走，才能保证慢指针到的是中间位置。

继续加油！：）