基于Floyd算法，快指针步长大于2时能否找到链表环起始节点？

答案是不行，没法直接沿用slow=1、fast=2那套「相遇后把慢指针移回表头，同速走直到相遇」的方法，原因如下：

先回忆下原方法为啥能行 #

假设链表开头到环起点有a个节点，环本身有b个节点：

• 快慢指针相遇时，慢指针走了a+m步（m是它在环里走的节点数，还没绕完一圈），快指针走了两倍的步数2*(a+m)
• 快指针比慢指针多走的步数肯定是环长的整数倍（毕竟一直在环里绕圈追），也就是2*(a+m) - (a+m) = n*b，化简后得到a + m = n*b
• 这时候把慢指针移回表头，它走a步就能到环起点；而快指针现在在环里的m位置，走a步的话，相当于m + a = m + n*b - m = n*b，刚好绕环n圈回到起点，所以两者会在环起点碰头。

步长大于2时为啥不行 #

比如快指针步长是3，慢指针还是1：

• 相遇时，慢指针走了t步，快指针走了3t步，路程差是2t，这个差得是环长b的整数倍，也就是2t = n*b
• 慢指针走的t步等于a+m，代入后得到2*(a+m) = n*b，化简成a = (n*b)/2 - m
• 这时候把慢指针移回表头走a步到起点，快指针在环里m位置走a步后的位置是(m+a) mod b = (n*b/2) mod b
• 只有当n是偶数时，这个位置才是环起点；如果n是奇数，那快指针走a步后会停在环的中间位置，和慢指针的相遇点就不是环起点了。

举个实际反例：环前1个节点，环长4（节点0→1→2→3→4→1），慢指针步长1，快指针步长3。

• 相遇时慢指针走了2步：0→1→2，快指针走了6步：0→3→1→4→2→4→2，两者在节点2相遇。
• 把慢指针移回0，同速走：慢指针走1步到1（环起点），快指针走1步到3，并未相遇；继续走3步后，慢指针到2→3→4→1，快指针到4→1→2→3，才在环起点碰头——显然不是第一次同速走就相遇，原方法失效。

步长大于2时的替代方案 #

虽然原方法用不了，但仍能通过其他方式找到环起点：

• 第一步：确认环存在：用快慢指针（只要快指针步长大于慢指针），两者相遇则说明链表有环
• 第二步：计算环长：相遇后，保持其中一个指针不动，另一个指针继续绕环移动，直到再次相遇，移动的步数就是环长b
• 第三步：查找环起点：用两个指针从表头出发，第一个指针先走b步，然后两个指针同速移动，相遇时的节点即为环起点

这个方法不依赖快慢指针的具体步长，适用于所有fast>slow的场景。

内容的提问来源于stack exchange，提问作者Иван Андросов