我是一名新生，在最近的一次采访中有人问我这个问题。
问题是---通过遍历链表的每个元素一次，找出单个链表在任何点是否是循环的
对此，我回答说，我们将在遍历另一个链表中的列表时存储每个节点的引用，对于正在测试的列表中的每个节点，我们将发现引用是否存在于我存储引用的列表中。
面试官说，他需要一个更优化的方法来解决这个问题。
有人能告诉我什么是解决这个问题的更优化的方法吗。
附言：我所说的循环在任何时候都是指这个。http://s22.postimg.org/g0iwevfnl/2013_06_30_15_56_34_362.jpg
面试官想看看你是否知道一个官方称为Floyd's cycle-finding algorithm或Tortoise and hare的技巧。
这个想法是在一个循环中推进两个指针，一个在每次迭代中移动两次，另一个只移动一次。如果快速移动的指针从后面追上慢速移动的指针，则列表有一个循环。
该算法检测O(n)时间和O(1)存储中的周期。"慢速"指针在列表中的遍历次数不超过一次，因此可以公平地说，该算法在一次遍历中就找到了答案。
在我看来，这种算法是一个糟糕的面试问题，因为除非你提前知道，否则很难当场想出。同时，这并不是一种使用广泛的算法，每个人都必须知道它，这让我想知道为什么有人会在采访中问它。
我怀疑面试官的目标是看看你是否知道Floyd循环查找算法。这样一个问题的目的是看看你是否理解数据结构的概念，比如列表、二叉树和散列。
你的答案的主要问题是，你给出的算法的复杂度为O（n^2），即遍历原始列表的O（n）*在每次迭代中检查第二个列表中是否存在每个节点的O（n）。
当面试官要求你优化答案时，你本可以建议用另一种比O（n）更快查找的数据结构来代替第二个链表。例如，二叉树具有O（logn）查找复杂度，哈希具有O（1）查找复杂程度（并非总是如此，但这是一个常见的假设），这比使用查找复杂度为O（n）的第二链表要快得多。
因此，O（n）解决方案是用哈希（即HashMap、HashSet等）替换第二个链表。
当然，Floyd循环查找算法是这个问题的一个更优雅的解决方案，因为它具有更好的内存复杂性（即不需要将访问的节点存储在内存中）。
更有效的方法是使用单个迭代器&检查是否存在指向null的节点。。。这种方法的效率应该是上述方法的两倍。
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