为何Floyd循环查找算法中龟兔需同起点？及入口定位问题

我理解当链表存在环时，如果快指针（hare）速度为2、慢指针（tortoise）速度为1，二者一定会相遇：因为环长为k的话，(2-1)*t（龟兔之间的间距）最终会被k整除。但我搞不懂，为什么要找到环的入口点，就必须让龟兔从同一个位置出发？

下面是我能正确运行的代码，但只要修改初始条件，入口点查找就会陷入死循环：

if(!head || head->next==nullptr) return nullptr;
ListNode* fast=head->next->next; 
ListNode* slow=head->next; // 如果改成slow=head或者fast=head->next，下面第二个循环会无限循环
while(fast!=nullptr && fast->next!=nullptr
    && slow!=nullptr && fast!=slow) {
    fast = fast->next->next;
    slow = slow->next;
}
if(fast!=nullptr && slow!=nullptr && fast==slow) {
    slow = head;
    while(fast!=slow){
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
} else { 
    return nullptr;
}

为什么初始位置不同会导致死循环？ #

核心问题出在环入口点的推导逻辑依赖快慢指针同起点出发，我们拆解这个逻辑：

同起点时的推导（正确情况）

假设：

• 链表头到环入口的距离为a
• 环的长度为k
• 快慢指针相遇时，慢指针总共走了a + b步（b是进入环后走的距离，0 ≤ b < k）
• 快指针速度是慢指针的2倍，所以总步数是2*(a + b)

由于快指针在相遇时已经绕环至少1圈，它的总步数也可以表示为a + b + n*k（n是绕环次数，n ≥ 1）。联立两个式子：

2*(a + b) = a + b + n*k

化简后得到：

a = n*k - b

这个等式的关键意义是：从链表头走到环入口的距离a，等于从相遇点出发绕环n圈后到入口的距离。所以当把慢指针移回链表头，快慢指针以相同速度前进时，必然会在环入口相遇。

不同起点时的矛盾（你的代码问题）

当快慢指针初始位置不同时，比如你的代码里slow=head->next、fast=head->next->next，相遇时的步数关系会被打破：

以你代码的初始状态为例，慢指针提前走了1步，快指针提前走了2步。假设相遇时，两个指针又各自走了t步：

• 慢指针总步数：1 + t
• 快指针总步数：2 + 2t

相遇时快指针比慢指针多走的步数是环长的整数倍（因为快指针在环里绕圈）：

(2 + 2t) - (1 + t) = m*k

化简得：

1 + t = m*k → t = m*k -1

此时慢指针的总位置是从head出发走了1 + t = m*k步，也就是在环内的某个位置，但这个位置到入口的距离不等于链表头到入口的距离a。这时候把慢指针移回head，两个指针同速前进，永远不会在入口相遇——比如举个具体的环结构：

链表结构：head → A → B → C → B（入口是B，环长2）

• 初始slow在A，fast在C
• 第一次循环：slow走到B，fast走到C→B→C
• 第二次循环：slow走到C，fast走到C→B→C，此时二者相遇
• 把slow移回head，开始同步前进：
  • slow路径：head → A → B → C → B...
  • fast路径：C → B → C → B...
    二者永远不会在入口B相遇，只会在B和C之间循环，导致死循环。

简单来说，初始位置不同会让相遇点不满足“头到入口距离=相遇点到入口距离”的核心条件，所以第二个循环永远找不到相等的节点，陷入死循环。

内容的提问来源于stack exchange，提问作者Lucar