檢查鏈表的循環性

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結束，如果列表確實是循環的，則該過程將在起始節點處結束。所以它就是一個具有恆定額外空間的線性時間算法。只需再次顛倒列表以恢復原始列表。