algorithm - 删除链表中的循环

Question

问题:如果链表中存在循环，如何找到循环的起始节点

方法:

(1)使用Hare-Tortoise算法，判断环路是否存在(这一步没有问题)

(2)设P为兔子和乌龟相遇的节点。设H为链表头指针。从H和P开始逐一遍历一个节点，直到相遇。

疑点:(2)背后的逻辑。从 H 和 P 一次遍历一步如何确保它们在循环开始时相遇？

引用资料:

Problem and Solution

Partially Explained Logic(Refer second approach in this blog)

Answer 1

令 T 为乌龟遍历的链接数，令 S 为到达循环之前遍历的链接数。

我们知道，沿着循环行驶 T 条路段会使您回到起点，因为乌龟和野兔分别经过 T 条路段和 2T 条路段后到达同一地点 P。如果你从 P 开始走 S 条路，这相当于从一开始就走 S 条路然后走 T 条路，这相当于只从一开始走 S 条路。

因此，当从链表开头开始的指针走了 S 个链接时，它到达了循环的开始，并与从 P 开始的指针相遇。