[解決済み】リンクリストのループを検出する方法は？

質問

Javaでリンクリスト構造を持っているとします。 これはNodeで構成されている。

class Node {
    Node next;
    // some user data
}

で、各Nodeは次のNodeを指します。ただし、最後のNodeはnextにnullを指定します。 つまり、最後のNodeはnullを持つ代わりに、その前に来たリスト内のいずれかのNodeへの参照を持つことになります。

の書き方はどうすればいいのでしょうか？

boolean hasLoop(Node first)

を返します。 true は、与えられたノードがループを持つリストの先頭であれば false それ以外の場合は？ どう書けば、一定の容量とそれなりの時間がかかるようになるのでしょうか？

ループを使ったリストがどのようなものか、写真で紹介します。

解決方法は？

を使用することができます。 Floydのサイクルファインディングアルゴリズム としても知られています。 かめとうさぎアルゴリズム .

リストへの参照を2つ用意し、それらを 異なる速度 . 一方を 1 ノードで、もう一方は 2 ノードがあります。

• リンクリストにループがある場合、それらは 意志 間違いなく を満たします。
• どちらか一方が 2つのリファレンス（またはその next ) になります。 null .

アルゴリズムを実装したJava関数です。

boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list

    while(true) {

        slow = slow.next;          // 1 hop

        if(fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false;          // next node null => no loop

        if(slow == null || fast == null) // if either hits null..no loop
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop
            return true;
    }
}