4

我是一个新人，在最近的一次采访中我被问到这个问题。

问题是——通过遍历链表的每个元素一次，找出单个链表是否在任何时候都是循环的。

对此我回答说，我们将在遍历另一个链表中的列表时存储每个节点的引用，并且对于正在测试的列表中的每个节点，我们会发现引用是否存在于我正在存储引用的列表中。

面试官表示，他需要更优化的方式来解决这个问题。

谁能告诉我解决此问题的更优化方法是什么。

PS：在任何时候，我的意思都是循环。http://s22.postimg.org/g0iwevfnl/2013_06_30_15_56_34_362.jpg

4

4 回答 4

9

面试官想看看你是否知道一个正式Floyd's cycle-finding algorithm或Tortoise and hare非正式的技巧。

这个想法是在一个循环中推进两个指针，一个每次迭代移动两次，另一个只移动一次。如果快速移动的指针从后面追上慢速移动的指针，则列表有一个循环。

该算法检测O(n)时间和O(1)存储周期。“慢”指针不超过一次遍历列表，因此可以公平地说该算法在一次遍历中找到了答案。

在我看来，这个算法是一个糟糕的面试问题，因为当场想出它有点困难，除非你提前知道它。同时，这不是一个被广泛使用到每个人都必须知道的算法，这让我想知道为什么有人会在采访中问到它。

于 2013-06-30T10:19:23.573 回答
3

我怀疑面试官的目标是看你是否知道弗洛伊德的循环查找算法。这个问题的目的是看看你是否理解数据结构的概念，如列表、二叉树和哈希。

您的答案的主要问题是您给出的算法的复杂度为 O(n^2)，即 O(n) 用于遍历原始列表 * O(n) 用于检查每个节点是否存在于第二个列表中，在每次迭代。

当面试官要求你优化你的答案时，你可能会建议用另一个比 O(n) 提供更快查找的数据结构替换第二个链表。例如，二叉树的查找复杂度为 O(logn)，散列的查找复杂度为 O(1)（并非总是如此，但这是一个常见的假设），这比使用具有查找复杂度的第二个链表要快得多的 O(n)。

所以一个 O(n) 的解决方案是用散列（即 HashMap、HashSet 等）替换你的第二个链表。

当然，Floyd 的寻环算法是解决这个问题的更优雅的方法，因为它具有更好的内存复杂度（即无需将访问过的节点存储在内存中）。

于 2014-01-25T16:54:39.417 回答
1

更有效的方法是使用单个迭代器并检查是否存在指向 null 的节点...这种方法的效率应该是上述方法的两倍。

于 2014-01-14T15:01:31.700 回答
0 
tempNode = list;

while((tempNode->next != list) && (tempNode->next != NULL))
     tempNode = tempNode->next;

if(tempNode->next == list)
   //list is circular
if(tempNode->next == NULL)
  //list is not circular

Above two conditions can be addressed in while loop also
于 2016-07-07T07:10:34.913 回答