如何確定循環在鏈表中發生的位置

Question

鏈表中可能存在循環，如何確定循環在鏈表中發生的位置。

Answer 1

如果有循環，它不再是鏈接列表。這是一個有向圖。該循環稱爲循環。

在圖表中查找循環的一種方法是遍歷列表，標記每個項目。如果你發現一個已經標記的項目，你已經找到了一個循環。

Answer 2

通過保存對節點的引用（比如列表頭部的引用）並開始遍歷列表，可以確定鏈表中是否存在循環。如果在某個時候你到達列表的末尾（一個空值），那麼就沒有循環。但是如果您碰巧再次找到之前保存的同一個節點，那麼您知道該列表是循環的。無論哪種方式，停止迭代。

例如，在Java這個方法會告訴你，如果Node個鏈表是循環：

public boolean isCircular(Node list) { 
    Node current = list; 
    while (current != null) { 
     if (current.next == list) 
      return true; 
     current = current.next; 
    } 
    return false; 
} 

編輯：

對於一般的解決方案，在找到一個任意的環鏈接列表，閱讀關於Floyd's cycle-finding algorithm（又名「烏龜和兔子」算法）。在以前的post中有一個很好的Java實現。