检查链表的循环性

Question

我需要一个方法，它将链表作为参数，如果它是循环的或不循环，则返回true或false。例如：圆形链表表示节点指向任何前一个节点。 我忘了告诉一些约束，我不能使用任何数据结构或动物内存分配。 我只能用局部变量和alogrithm可以在n个步骤，有人跟我说要做

Answer 1

我相信你正在寻找Floyd's Cycle-Finding Algorithm。有一个比我能通过here更好的解释。

在C和Scheme中还有几个实现，其文档大小为here。

Answer 2

标准哈希计数适用（我现在想用两个指针？）：

 
function has_loop(list): 
    foreach node in list: 
     address = address_of(node.next); 
     element = hashtable.get(address); 
     if (element == NULL): 
      hashtable.put(address) 
     else: 
      return true 
    return false 

编辑：根据已接受的答案的第二个链接，这可行但效率低下，这意味着有很多更有效的解决方案。

Answer 3

这是微不足道的。

previousnodes ← set() 
previousnodes.add(firstnode) 
currentnode ← firstnode.next 
while (currentnode in previousnodes) || (currentnode != null): 
    previousnodes.add(currentnode) 
    currentnode ← currentnode.next 
when (currentnode = 0) return false 
return true 

Answer 4

我自己遇到了这个问题的一个优雅的解决方案，并忍不住在这里发布（尽管我猜原版海报可能现在已经毕业了）。从开始节点开始，开始反转列表。如果列表不是循环的，则该过程将以Null结束，如果列表确实是循环的，则该过程将在起始节点处结束。所以它就是一个具有恒定额外空间的线性时间算法。只需再次颠倒列表以恢复原始列表。