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人目の人の速度が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;
}

この方法は、「フロイドの周期探索アルゴリズム」の「亀とウサギのアルゴリズム」としても知られています。


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

サイクルを削除するためのいくつかの方法を見てみましょう。 ** これらの方法はすべて、サイクル検出に「Flyodsサイクル検出アルゴリズム」が使用されていることを前提としており、その上に構築されています。


3.1. 強引な

高速反復子と低速反復子がサイクルのある時点で出会ったら、もう1つ反復子（

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. 高速反復子と低速反復子が出会ったら、サイクルの長さを見つけます.

これは、訪問したノードの数を維持しながら、最初のポインタに到達するまでもう一方のイテレータを（通常の速度で1つずつ繰り返しながら）続けながら、イテレータの1つを所定の位置に保持することによって実行できます。

これは

l

としてカウントされます
。リストの先頭に2つのイテレータ（

ptr1

と

ptr2

）を置きます。

反復子の1つを移動（

ptr2

）

l

ステップ
。今度は両方のイテレータを、それらが最初に出会うまで繰り返します。

ループし、続いてサイクルの終わりを見つけて、それを

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

サイクル完了し、最初のポインタを満たすことになります。サイクルの始めに。この洞察を使用して、アルゴリズムを定式化できます。

  1. ループを検出するには、「Flyodsサイクル検出アルゴリズム」を使用してください. ループの場合

存在する場合、このアルゴリズムはループの内側の点で終了します（これを呼び出します。
ミーティングポイント）
。 2つのイテレータを取ります。1つはリストの先頭（

it1

）、もう1つはリストの先頭にあります。

ミーティングポイント（

it2

）
。両方のイテレータを同じ速度で走査する

  1. 頭からのループの距離は（上で定義されたように）kなので、

頭から始まるイテレータは

k

ステップ後にサイクルに達する
。

k

ステップでは、反復子

it2

はループの

m – 1

サイクルをたどります。

このポインタはすでに遠くにあったので
この余分な距離を横切って、サイクルの始めから

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結論

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

最後に、「Flyodsサイクル発見アルゴリズム」を使用して検出されたサイクルを削除する3つの方法も示しました。

完全なコード例はhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-2[over on Github]から入手できます。