根据弗洛伊德循环查找算法,龟兔赛跑点解释了链表的循环性。
为了找到循环中的起始节点,我们将乌龟指针初始化为列表的头部,并开始将 hare 和 tortoise 指针递增一个单位。它们相交的点表示循环的起始节点。
请告诉我在给定情况下它是如何工作的。
链接列表的流程如下:
1->2->3->4->5->6->7->8->3
最佳答案
让我们看看。
你把兔子和乌龟放在 1,让它们跑,兔子的速度是乌龟的两倍。
在第零步,两者都为1。在第一步,乌龟移动到2,兔子移动到3,依此类推。
1 1
2 3
3 5
4 7
5 3
6 5
7 7
所以兔子和乌龟在 7 点相遇。
现在把乌龟放在起点,让它们再次跑,现在速度相同。
1 7
2 8
3 3
所以他们确实在循环的第一个元素相遇了。
这就是给定情况的运作方式。
关于algorithm - 我们如何找到链表中循环的起始节点?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10880672/