algorithm - 解决循环链表的方法是什么？

Question

给定一个循环链表，实现一个在循环开始时返回节点的算法。

定义： Cicular Link list：一个（损坏的）链表，其中一个节点的next指针指向一个更早的节点，从而在链表中形成一个循环。

示例：输入：A->B->C->D->E->C[与之前相同的 C] 输出：C

Answer 1

您可以使用乌龟和兔子算法：

1. 从两个指针开始，调用一个 thetortoise和另一个 thehare
2. 在每个时间步，乌龟前进一次，兔子前进两次
3. 重复直到它们相等

这为您提供了循环内的元素。要找到循环的开头：

1. 让乌龟一步一步前进，数数步数
2. 停下来，直到你到达野兔

这将允许您找到循环的长度。然后你只需要一步一步size-length来找到开始，size你的“链表”中的元素数量在哪里。

这也称为弗洛伊德循环检测算法。

Answer 2

检测循环的常用算法是让两个指针/迭代器在列表中前进，一个前进一个元素，另一个前进两个。如果两个迭代器曾经指向同一个元素，则列表中有一个循环。

找到循环后，您可以收集集合中的所有元素，然后从列表的开头开始，直到找到该集合中的元素。这个元素可以被认为是循环的“开始”

Answer 3

最简单的算法是使用数据结构来存储已经访问过的元素。您可以使用哈希表（大约 O(n)）或简单的排序数组 O(nlog(n))。

您还可以假设您的链表是一个图形，并使用常用的循环检测算法之一。