リンクリスト内でループが発生する場所を特定する方法

Question

リンクリスト内にループが存在する可能性があります。リンクされたリスト内でループが発生する場所を特定する方法があります。

Answer 1

ループがある場合は、もはやリンクされたリストではありません。有向グラフです。ループはサイクルと呼ばれます。

グラフでサイクルを見つける1つの方法は、リストを反復して各項目に印を付けることです。既にマークされているアイテムが見つかった場合は、サイクルが見つかりました。

Answer 2

リンクされたリストにループがあるかどうかは、ノードへの参照（たとえば、リストの先頭にあるもの）を保存し、リストを反復処理することで確認できます。ある時点でリストの終わり（ヌル値）に達すると、ループはありません。しかし、以前に保存されていた同じノードを再び見つけた場合、そのリストは循環的であることがわかります。いずれにしても、反復を停止します。

Node秒のリンクリストが円形である場合たとえば、Javaでこのメソッドはあなたを教えてくれます：で、任意のループを見つけるため

一般的な解決のために：

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

EDITリンクされたリストは、Floyd's cycle-finding algorithm（別名「カメとハレ」アルゴリズム）について読んでください。これまでのpostには、Javaの優れた実装があります。