リンクされたリストを時計回りに回転させる JavaScript プログラム-jsチュートリアル-php.cn

リンクされたリストを時計回りに回転させる 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) になります。

＃＃＃結論は＃＃＃