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

Question

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

Answer 1

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

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

Answer 2

リンクされたリストにループがあるかどうかは、ノード (たとえば、リストの先頭にあるノード) への参照を保存し、リストの反復処理を開始することで確認できます。ある時点でリストの最後 (null 値) に達した場合、ループはありません。しかし、以前に保存された同じノードが再び見つかった場合は、リストが循環していることがわかります。いずれにせよ、繰り返すのはやめましょう。

たとえば、Java では、このメソッドはNodes のリンクされたリストが循環しているかどうかを示します。

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

編集 ：

リンクされたリストで任意のループを見つけるための一般的な解決策については、フロイドのサイクル検索アルゴリズム(別名「カメとウサギ」アルゴリズム) について読んでください。この以前の投稿には、優れた Java 実装があります。