pointers - 查找链表的结尾

Question

我正在查看面试问题，我遇到了“您如何确定链表是否有结束？（即列表不是循环）。” 它提供了一个解决方案（一次遍历一个和两个节点，并查看指针是否相等）。

难道我们不能只保留我们开始的指针，看看在遍历它时是否再次击中那个指针吗？或者那行不通？

Answer 1

那是行不通的：链表可能包含一个不包含第一个指针的循环。

请记住，链表中的一个节点可以被多个其他节点链接！

Answer 2

Couldn't we just keep the pointer that we start at and see if 
while traversing it, we ever hit that pointer again?

不，请参阅下面的案例。您将只遍历循环而不会碰到列表的开始节点

另一种查找是否存在循环的方法：

如果你把列表倒过来，记住最初的节点，你就会知道如果你回到第一个节点，就会知道有一个循环。虽然有效，但此解决方案更改了列表并且不适合多线程应用程序。

Answer 3

取两个指针，一个应该一次遍历列表一个节点，另一个应该一次遍历列表 2 个节点。如果在任何时候它们相遇（两个指针都指向同一个节点）。这意味着它是一个循环链表并且没有结束。