リンクリストの循環性をテストする

投稿日: 2019-10-19 2022-10-14
タグ: Java

1. 序章

単一リンクリストは、null参照で終わる接続ノードのシーケンスです。ただし、一部のシナリオでは、最後のノードが前のノードを指している場合があり、効果的にサイクルが作成されます。

ほとんどの場合、これらのサイクルを検出して認識できるようにする必要があります。この記事では、まさにそのことに焦点を当てます–サイクルを検出し、潜在的に削除します。

2. サイクルの検出

次に、リンクリストでサイクルを検出するためのいくつかのアルゴリズムを調べてみましょう。

2.1. ブルートフォース– O（n ^ 2）時間計算量

このアルゴリズムでは、2つのネストされたループを使用してリストをトラバースします。外側のループでは、1つずつトラバースします。内側のループでは、頭から開始し、その時点までに外側のループが通過したのと同じ数のノードを通過します。

外側のループが訪問したノードが内側のループによって2回訪問された場合、サイクルが検出されました。逆に、外側のループがリストの最後に達した場合、これはサイクルがないことを意味します：

public static <T> boolean detectCycle(Node<T> head) {
    if (head == null) {
        return false;
    }

    Node<T> it1 = head;
    int nodesTraversedByOuter = 0;
    while (it1 != null && it1.next != null) {
        it1 = it1.next;
        nodesTraversedByOuter++;

        int x = nodesTraversedByOuter;
        Node<T> it2 = head;
        int noOfTimesCurrentNodeVisited = 0;

        while (x > 0) {
            it2 = it2.next;

            if (it2 == it1) {
                noOfTimesCurrentNodeVisited++;
            }

            if (noOfTimesCurrentNodeVisited == 2) {
                return true;
            }

            x--;
        }
    }

    return false;
}

このアプローチの利点は、一定量のメモリが必要になることです。欠点は、大きなリストが入力として提供される場合、パフォーマンスが非常に遅くなることです。

2.2. ハッシュ– O（n）スペースの複雑さ

このアルゴリズムでは、すでにアクセスしたノードのセットを維持します。ノードごとに、セットに存在するかどうかを確認します。そうでない場合は、セットに追加します。セット内にノードが存在するということは、すでにノードにアクセスしており、リスト内のサイクルの存在を前面に押し出していることを意味します。

セットにすでに存在するノードに遭遇したとき、私たちはサイクルの始まりを発見したでしょう。これを発見した後、以下に示すように、前のノードのnextフィールドをnullに設定することで、サイクルを簡単に中断できます。

public static <T> boolean detectCycle(Node<T> head) {
    if (head == null) {
        return false;
    }

    Set<Node<T>> set = new HashSet<>();
    Node<T> node = head;

    while (node != null) {
        if (set.contains(node)) {
            return true;
        }
        set.add(node);
        node = node.next;
    }

    return false;
}

このソリューションでは、各ノードに1回アクセスして保存しました。これは、O（n）時間計算量とO（n）空間計算量に相当し、平均して、大きなリストには最適ではありません。

2.3. 高速および低速ポインタ

サイクルを見つけるための次のアルゴリズムは、メタファーを使用して最もよく説明できます。

2人がレースをしているレーストラックを考えてみましょう。 2人目の速度が1人目の速度の2倍であることを考えると、2人目の人は1人目の2倍の速度でトラックを周回し、ラップの開始時に再び1人目の人に会います。

ここでは、低速イテレータと高速イテレータ（2倍の速度）と同時にリストを反復処理することにより、同様のアプローチを使用します。両方のイテレータがループに入ると、最終的にはある時点で出会います。

したがって、2つのイテレータがいずれかの時点で出会った場合、サイクルに遭遇したと結論付けることができます。

public static <T> CycleDetectionResult<T> detectCycle(Node<T> head) {
    if (head == null) {
        return new CycleDetectionResult<>(false, null);
    }

    Node<T> slow = head;
    Node<T> fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            return new CycleDetectionResult<>(true, fast);
        }
    }

    return new CycleDetectionResult<>(false, null);
}

CycleDetectionResult は、結果を保持するための便利なクラスです。 boolean 変数は、サイクルが存在するかどうかを示し、存在する場合は、サイクル内のミーティングポイントへの参照も含みます。：

public class CycleDetectionResult<T> {
    boolean cycleExists;
    Node<T> node;
}

この方法は、「カメとウサギのアルゴリズム」または「Flyodsサイクル検出アルゴリズム」としても知られています。

3. リストからのサイクルの削除

サイクルを削除するためのいくつかの方法を見てみましょう。 これらの方法はすべて、「Flyods Cycle-Finding Algorithm」が循環検出に使用され、その上に構築されていることを前提としています。

3.1. 強引な

サイクルのある時点で高速イテレータと低速イテレータが出会ったら、もう1つのイテレータ（ ptr など）を取得して、リストの先頭にポイントします。 ptrでリストの反復を開始します。各ステップで、待ち合わせ場所からptrに到達できるかどうかを確認します。

これは、 ptr がループの先頭に到達したときに終了します。これは、 ptr がループに入り、待ち合わせ場所から到達可能になる最初のポイントであるためです。

ループの開始（ bg ）が検出されると、サイクルの終了（次のフィールドが bg を指すノード）を見つけるのは簡単です。次に、このエンドノードの次のポインタが null に設定され、サイクルが削除されます。

public class CycleRemovalBruteForce {
    private static <T> void removeCycle(
      Node<T> loopNodeParam, Node<T> head) {
        Node<T> it = head;

        while (it != null) {
            if (isNodeReachableFromLoopNode(it, loopNodeParam)) {
                Node<T> loopStart = it;
                findEndNodeAndBreakCycle(loopStart);
                break;
            }
            it = it.next;
        }
    }

    private static <T> boolean isNodeReachableFromLoopNode(
      Node<T> it, Node<T> loopNodeParam) {
        Node<T> loopNode = loopNodeParam;

        do {
            if (it == loopNode) {
                return true;
            }
            loopNode = loopNode.next;
        } while (loopNode.next != loopNodeParam);

        return false;
    }

    private static <T> void findEndNodeAndBreakCycle(
      Node<T> loopStartParam) {
        Node<T> loopStart = loopStartParam;

        while (loopStart.next != loopStartParam) {
            loopStart = loopStart.next;
        }

        loopStart.next = null;
    }
}

残念ながら、このアルゴリズムは、リストが大きく、サイクルが大きい場合にもパフォーマンスが低下します。これは、サイクルを複数回トラバースする必要があるためです。

3.2. 最適化されたソリューション–ループノードのカウント

最初にいくつかの変数を定義しましょう：

n=リストのサイズ
k=リストの先頭からサイクルの開始までの距離
l=サイクルのサイズ

これらの変数の間には、次の関係があります。 k + l = n

このアプローチでは、この関係を利用します。より具体的には、リストの先頭から開始するイテレータがすでに l ノードを移動した場合、リストの最後に到達するにはkより多くのノードを移動する必要があります。

アルゴリズムの概要は次のとおりです。

高速と低速のイテレータが出会ったら、サイクルの長さを見つけます。これは、一方のイテレータを所定の位置に保持し、もう一方のイテレータを最初のポインタに到達するまで（通常の速度で1つずつ繰り返し）継続し、アクセスしたノードの数を維持することで実行できます。これはlとしてカウントされます
リストの先頭にある2つのイテレータ（ptr1とptr2）を使用します。イテレータ（ ptr2 ）lステップの1つを移動します
次に、ループの開始時に出会うまで両方のイテレータを反復し、その後、サイクルの終了を見つけて、nullをポイントします。

これが機能するのは、ptr1がループからkステップ離れており、 lステップだけ進んだptr2、にもが必要だからです。 ] k ステップでループの終わりに到達します（ n – l = k ）。

そして、これが単純で潜在的な実装です。

public class CycleRemovalByCountingLoopNodes {
    private static <T> void removeCycle(
      Node<T> loopNodeParam, Node<T> head) {
        int cycleLength = calculateCycleLength(loopNodeParam);
        Node<T> cycleLengthAdvancedIterator = head;
        Node<T> it = head;

        for (int i = 0; i < cycleLength; i++) {
            cycleLengthAdvancedIterator 
              = cycleLengthAdvancedIterator.next;
        }

        while (it.next != cycleLengthAdvancedIterator.next) {
            it = it.next;
            cycleLengthAdvancedIterator 
              = cycleLengthAdvancedIterator.next;
        }

        cycleLengthAdvancedIterator.next = null;
    }

    private static <T> int calculateCycleLength(
      Node<T> loopNodeParam) {
        Node<T> loopNode = loopNodeParam;
        int length = 1;

        while (loopNode.next != loopNodeParam) {
            length++;
            loopNode = loopNode.next;
        }

        return length;
    }
}

次に、ループ長を計算するステップを排除することさえできる方法に焦点を当てましょう。

3.3. 最適化されたソリューション–ループノードをカウントせずに

高速ポインタと低速ポインタが移動した距離を数学的に比較してみましょう。

そのためには、さらにいくつかの変数が必要です。

y =サイクルの最初から見た、2つのイテレータが出会うポイントの距離
z =サイクルの終わりから見た、2つのイテレーターが交わる点の距離（これは l – y にも等しい）
m=低速イテレータがサイクルに入る前に高速イテレータがサイクルを完了した回数

他の変数を前のセクションで定義したものと同じに保ちながら、距離方程式は次のように定義されます。

スローポインターの移動距離=k （自転車の頭からの距離）+ y （自転車内の合流点）
高速ポインターが移動した距離=k （ヘッドからのサイクルの距離）+ m （低速ポインターが入る前に高速ポインターがサイクルを完了した回数）* l （サイクル長）+ y （サイクル内の合流点）

高速ポインタの移動距離は低速ポインタの2倍であることがわかっているため、次のようになります。

k + m * l + y = 2 *（k + y）

これは次のように評価されます。

y = m * l – k

l から両側を引くと、次のようになります。

l – y = l – m * l + k

または同等に：

k =（m – 1）* l + z（ここで、l – yは上記で定義されたzです）

これはにつながります：

k =（m – 1）完全なループ実行+追加の距離z

つまり、リストの先頭に1つのイテレータを保持し、ミーティングポイントに1つのイテレータを配置し、それらを同じ速度で移動すると、2番目のイテレータは m –1サイクルを完了します。ループして、サイクルの開始時に最初のポインターを満たします。この洞察を使用して、アルゴリズムを定式化できます。

「FlyodsCycle-FindingAlgorithm」を使用してループを検出します。ループが存在する場合、このアルゴリズムはループ内のポイントで終了します（これをミーティングポイントと呼びます）
リストの先頭（ it1 ）とミーティングポイント（ it2 ）の2つのイテレータを使用します。
両方のイテレータを同じ速度でトラバースします
ヘッドからのループの距離はk（上記で定義）であるため、ヘッドから開始されたイテレータは、kステップの後にサイクルに到達します。
k ステップでは、イテレータit2はループのm–1サイクルと余分な距離zをトラバースします。このポインタはすでに存在していたためサイクルの開始からzの距離で、この余分な距離 z を移動すると、サイクルの開始時にも移動します。
両方のイテレータはサイクルの開始時に会合し、その後、サイクルの終了を見つけてnullを指すことができます。

これは実装できます：

public class CycleRemovalWithoutCountingLoopNodes {
    private static <T> void removeCycle(
      Node<T> meetingPointParam, Node<T> head) {
        Node<T> loopNode = meetingPointParam;
        Node<T> it = head;

        while (loopNode.next != it.next) {
            it = it.next;
            loopNode = loopNode.next;
        }

        loopNode.next = null;
    }
}

これは、リンクリストからサイクルを検出および削除するための最も最適化されたアプローチです。

4. 結論

この記事では、リスト内のサイクルを検出するためのさまざまなアルゴリズムについて説明しました。計算時間とメモリスペースの要件が異なるアルゴリズムを調べました。

最後に、「FlyodsCycle-FindingAlgorithm」を使用して検出されたサイクルを削除する3つの方法も示しました。

完全なコード例は、Githubでから入手できます。

getdocs

13036