リンクされたリストを時計回りに回転させる JavaScript プログラム

JavaScript のリンク リストの基本構造は、JavaScript のクラスを使用して作成でき、ノードをある位置から別の位置に移動して回転させることができます。この記事では、JavaScript プログラミング言語でリンク リストを時計回りに回転する方法を学びます。これらの概念をより深く理解するためのコードを見ていきます。

この問題では、リンク リストが与えられており、それを時計回りに回転する必要があります。これは、すべての移動で最後の要素を最初に配置する必要があり、k 回回転する必要がある場合は、リンクされたリストの先頭または開始ノードの前に最後の要素を配置する必要があることを意味します。前に見たリンク リストを作成するには、データをバインドするクラスと次の要素へのポインターが必要です。

リンクリスト構造

＃＃＃例＃＃＃

まず、現在のノードの値と次のノードへのポインターを格納するクラス ノードを作成します。その後、リンク リストの作成を支援するプッシュ関数を作成し、最後にリンク リストの印刷を支援する表示関数を作成します。まずコードを見てみましょう -

リーリー

上記のコードでは、class キーワードを使用してクラスを作成し、「this」キーワードを使用してデータとクラス コンストラクター内の次のノードへのポインターを保存するセクションを作成しました。

その後、2 つのパラメーターを取るプッシュ関数を定義します。最初のパラメーターはリンク リストの先頭、2 番目のパラメーターはリンク リストに追加する新しいノードのデータです。関数では、新しいノードを作成し、そこに値を保存します。先頭が空であるかどうかを確認し (最初の要素を追加することを意味します)、単純に新しいノードを返します。それ以外の場合は、ループを使用してリンクされたリストの末尾に移動し、そこに新しいノードを追加します。 p>

問題の解決策

クラスを作成し、必要な基本関数を定義した後、メイン関数に進み、最後の k 要素をリンク リストの先頭に移動する関数を定義します。これは、リンク リストの回転を表します。最後の k 要素を最初の要素に追加する方法は 2 つあります。これは、リンク リストの右回転に相当します。たとえば、-

です。

リンクされたリストが与えられます: 1 -> 2 -> 3 -> 4 -> 5 -> null

リストされたリンクを時計回りに 1 回回転させたいので、次のようになります -

リーリー

同様に、リンク リストを 3 回転すると、リンク リストは次のようになります -

リーリー

リンク リストの前に最後の要素を追加するには、1 つずつまたは一度に追加する 2 つの方法があります。

リンクされたリストを 1 つずつ回転します

＃＃＃例＃＃＃

このメソッドでは、最後のノードに移動し、それを前のヘッド ノードに移動して、ヘッド ノードを更新します。まずコードを見てみましょう -

リーリー

上記のコードでは、上で定義した基本関数のリンク リスト コードを使用し、リンク リストを回転する新しい関数を追加するだけです。

関数rotateでは、最初にwhileループを使用してリンク・リストをk回走査し、各反復でリンク・リストの最後から2番目の要素に到達します。次に、リンク リストの最後の要素をリンク リストから削除し、リンク リストの先頭の前に配置します。最後に、新しいヘッダーを返し、display 関数を使用して新しいリンクされたリストを表示します。

時間と空間の複雑さ

リンク リストを k 回移動し、リンク リストのサイズは N であるため、プログラムの全体的な時間計算量は O(N*K) になります。さらに、余分なスペースを使用していないため、プログラムのスペース複雑さは O(1) であり、これは定数です。

リンクされたリストを 1 回回転します

前のコードでは、リンク リストをより適切に移動し、リンク リストのサイズを取得できるように、要素を 1 つずつ追加しましたが、O(N*N) 時間がかかりました。その後、リンク リストを再度走査して最後の k 要素を取得し、それらをリンク リストの先頭に追加します。これにより、プログラムの時間計算量は O(1) になります。

＃＃＃結論は＃＃＃

このチュートリアルでは、JavaScript プログラミング言語でリンク リストを時計回りに回転する方法を学びました。概念を深く理解するためにコードを見てきました。 JavaScript のリンク リストの基本構造は、JavaScript のクラスを使用して作成でき、ノードをある位置から別の位置に移動して回転させることができます。プログラムの時間計算量は O(N*N) ですが、これはさらに O(N) まで改善できますが、プログラムの空間計算量は O(1) です。

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