リンクされたリスト内のループの長さを見つけるための JavaScript プログラム

このプログラムでは、ループが含まれている可能性のあるリンク リストを取得します。ループが存在するかどうか、そしてループのサイズはどれくらいかを調べなければなりません。コードを使用してループの長さを求める非常に有名な方法を使用し、その時間と空間の複雑さについて説明してみましょう。

問題の紹介

この質問では、上で見たように、ループが含まれる場合と含まれない場合があるリンク リストが与えられます。ループが存在する場合はループの長さを見つける必要があり、そうでない場合はゼロを返さなければなりません。ループはありません。フロイドループ法を使用してループを見つけ、そのサイズを確認します。たとえば、リンクされたリスト -

8 を含むノードから 4 を含むノードまでのサイクルがあります。これは、8 が 4 と接続されて、長さ 5 のサイクルを形成していることを意味します。これを検出する必要があります。

この質問では、フロイド ループ法を使用してループを検出し、次に長さ検索の概念を使用してループの長さを見つけます。まず問題の基本的な手順を見て、次にフロイト法と長さ法に進みます。

まず、リンク リスト ノードの基本構造を提供するクラスを作成し、その中でノード値を初期化するコンストラクターを定義します。
次に、指定されたリンク リストに要素をプッシュする関数を作成します。
上記の方法を使用してリンク リストを作成し、最後のノードを別のノードにリンクして、その中にループを形成します。
フロイトのアルゴリズム

このアルゴリズムでは、リンク リストをトラバースします。リンク リストに入ると、どのノードからも抜け出すことはできません。これは、リンク リストの円形部分に 2 つのポインタがあり、1 つのポインタが一度に 1 つのノードを移動し、もう 1 つのポインタが一度に 2 つのノードを移動すると、それらはある時点で出会うことを意味します。

アルゴリズムを実装した後、関数を呼び出してループが存在するかどうかを確認します
ループがある場合は、another 関数を呼び出してループの長さを調べます。
一方、戻ってループがないことを出力します。

• ＃＃＃例＃＃＃
次の例では、リンク リストを定義し、それに 8 つのノードを追加します。ノード 8 をノード 4 に接続することで、リンク リスト内にループを形成します。したがって、5 つのノードのループが形成されます。

時間と空間の複雑さ

上記のコードでは、完全なリンク リストを 1 回だけ走査し、ループ部分は最大 3 回走査するため、時間計算量は線形になります。したがって、上記のコードの時間計算量は線形、つまり O(N) です。ここで、N はリンク リストのサイズです。

余分なスペースを使用していないため、プログラムの時間計算量は O(1) です。

このチュートリアルでは、JavaScript 言語で概念を実装することにより、リンク リスト内に存在するループの長さを見つける方法を学習しました。 Floyd のループ検索アルゴリズムを使用して、指定されたリンク リスト内のループを検索し、次に while ループを使用してループを反復処理し、その長さを見つけました。上記のコードの時間計算量は O(N)、空間計算量は O(1) です。

以上がリンクされたリスト内のループの長さを見つけるための JavaScript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。