删除链表中的循环

Removing Cycle in Linked List

问题:如果链表中存在循环,则查找循环的起始节点

方法:

(1)使用龟兔赛跑算法,判断环是否存在(这一步没有问题)

(2)设 P 是兔子和乌龟所在的节点 meets.Let H 是链接上的头指针 list.Traverse 从 H 和 P 一次一个节点直到它们相遇。

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

参考文献:

Problem and Solution

Partially Explained Logic(Refer second approach in this blog)

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

我们知道,沿着循环行驶 T 条路段会使您回到起点,因为乌龟和兔子分别经过 T 条路段和 2T 条路段后到达同一个点 P。如果从P出发走S路,相当于从起点走S路,然后走T路,相当于从起点走S路。

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