0

リンクされたリストでサイクルを検出するための次のコードがあります。

public Class Node {
    Object data;
    Node next = null;
}

boolean containCycle() {
    boolean retVal = true;
    Node head = this;
    Node slower = head;
    Node faster = head;

    if(faster != null && faster.next != null) {
        faster = faster.next;
    } else {    // there is only one element or zero element
        retVal = false;
    }

    if (faster.next != null) {
        faster = faster.next;
    } else {    // there are only 2 elements
        retVal = false;
    }

    while (slower != faster && slower != null && faster != null) {
        faster = (faster.next != null && faster.next.next != null) ? faster.next.next : null;
        slower = (slower.next != null) ? slower.next : null;
    }

    if (slower == faster) {
        retVal = true;
        System.out.printf("The two pointers meet at: %d\n", faster.data);
    } else {
        retVal = false;
    }

    if (retVal) {    // this is the part for detecting where the loop begins
        slower = head;
        while(slower.next != faster.next) {
            slower = slower.next;
            faster = faster.next;
        }
        System.out.println("The cycle starts at: " + slower.data);
    }

    return retVal;
}

このコードは、コード内でコメントしたループの開始位置を実際に検出し始める部分まで正常に実行されます。どういうわけか、これは無限ループに陥ります。

これは、Java の参照渡しに関係しているのではないでしょうか? headループを検出していたときに参照する値を更新していますか? 私はここで本当にアイデアがありません。助けてください！

4

1 に答える 1

0

正確なアルゴリズムはわかりませんが、次の方法で待ち合わせ場所を見つけることができます。

低速と高速が出会うノードをミーティングポイントと呼びましょう。

頭から始まる 2 つのポインターと、ミーティング ポイントから始まる 2 つのポインターを用意します。そして、頭からミーティングポイントまでトラバースする必要があるノードの数（これを と呼びましょうa）と、ミーティングポイントの次のノードからミーティングポイントまでの数を数えます。(これを count と呼びましょう b)

これら 2 つのカウントの違い|a-b|は、共通部分を表しています。(つまり、ループの開始点と低速と高速の合流点の間の部分)。

2 つのポインターをリセットします。1 つは頭、もう 1 つはミーティング ポイント + 1 です。

たとえば、 の場合a>b、ヘッド|a-b|タイムからポインターを移動します。それ以外の場合は、ポインターをミーティング ピオント + 1|a-b|回から移動します。

次に、2 つのポインターが合うまで一緒に移動します。

これを説明する別の方法

あなたが探しているのは、2 つのリンクされたリストがあり、それらがいくつかのノードで結合し、そのノードを識別する必要がある場合と似ているためです。あなたが持っているのは、2 つのリンクされたリストの開始点だけです。

したがって、head1 から開始し、リストの最後までカウントします。次に、head2 から開始し、リストの最後までカウントします。

長さの違いを計算します。パス差分時間を長くします。そして、2 つのポインターが出会うまで、短いパス head と diff からポインターの移動を開始します。

これは本質的に、他のケースで行っていることと同じです。

于 2013-02-21T05:21:33.463 に答える