通过只遍历一次测试单向链表是否为循环链表

Question

我是一名新手，最近在面试中被问到了这个问题。

问题是 --- 通过遍历单链表的每个元素，仅找一次就能找到单链表在任何点上是否是循环的。

对于这个问题，我的回答是：我们将在遍历列表时存储每个节点的引用到另一个链表中，并且对于要测试的列表中的每个节点，我们将查找该引用是否存在于我们正在存储引用的列表中。

面试官说他需要一种更优化的方法来解决这个问题。

请问有人可以告诉我解决这个问题的更优化的方法吗？

PS：在任何点上循环的意思是这样的。 http://s22.postimg.org/g0iwevfnl/2013_06_30_15_56_34_362.jpg

- user1589754

---

“在任何时候”是什么意思？ - user1944441

就像这样的东西 http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/333px-6n-graf.svg.png? - user1944441

我所说的“在任何点上的圆形”是指这个——http://s22.postimg.org/g0iwevfnl/2013_06_30_15_56_34_362.jpg - user1589754

你有询问过澄清的问题吗？弗洛伊德算法被排除了吗？你能修改这个列表吗？ - Joni

不，我不能修改这个列表。我们只能遍历它。因为需要两次遍历列表，所以乌龟和兔子算法被直接排除了。 - user1589754

Answer 1

面试官想要知道您是否了解一种被正式称为Floyd's cycle-finding algorithm，或非正式称为“乌龟和兔子”的技巧。

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

该算法以O(n)时间和O(1)存储检测循环。 "慢"指针最多只需通过列表一次，因此可以说该算法在单次遍历中找到答案。

在我看来，这个算法并不是一个好的面试问题，因为除非事先知道它，否则很难当场想出来。同时，这不是一种如此广泛使用的算法，以至于每个人都必须知道它，这让我想知道为什么会在面试中询问它。

- Sergey Kalinichenko

---

只需遍历链表的每个元素一次。 - Luchian Grigore

但是先生，它使用了两个指针。问题明确提到每个元素只遍历一次。 - user1589754

@LuchianGrigore 我非常确定面试官要求对列表进行单次遍历，而不是对每个元素进行单次遍历。由于慢指针最多只通过列表一次，我认为可以说 Floyd 的循环检测算法在单次遍历中找到循环。 - Sergey Kalinichenko

@Tomas 尽管快指针可能会多次访问同一个元素，但它会在找到循环的同时停止，这发生在慢指针的单一路径中，或者是 O(λ + μ)（请参见答案中链接的文章）。 - Sergey Kalinichenko

但整个算法应该是单次遍历，因此您不能将快指针排除在外。您不能仅仅说“慢指针是单次遍历”。这样我可以构建任何我想要的算法（二次方、遍历n次等），然后只需添加一个慢指针并说“是的，它是单次遍历”。这个算法不是单次遍历。 - Tomas

Answer 2

我怀疑面试官的目的并不是考察你是否了解Floyd循环查找算法。这类问题的目的是看你是否理解数据结构的概念，例如列表、二叉树和哈希表。

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

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

因此，一个O(n)的解决方案是将第二个链接列表替换为哈希表（即HashMap、HashSet等）。

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

- nbilal

---

我同意你的答案 - 知道弗洛伊德算法是一个特殊的技巧，如果你不知道这个技巧，如何解决问题就成了主要挑战。 - oneday

Answer 3

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

- Ranjan

---

如果列表中有一个循环，那不就会变成无限循环了吗？ - kaushal

Answer 4

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

- krish

---

请尽量避免只把代码作为答案进行提交，尝试解释它的作用以及原因。你的代码对于那些没有相关编程经验的人来说可能并不明显。 - Frits