単一リンクリストが回文であるかどうかをチェックする JavaScript プログラム

一方向リンク リストは、不連続な方法でメモリに格納される線形データ構造です。各ブロックは、次のブロック (ブロックとも呼ばれます) のアドレスを保存することによってメモリに格納されます。ノード）に接続します。回文は文字や数字などのセットとして解釈でき、表からも裏からも同じように読めます。単一リンクされたリストを取得し、ノードに格納されている値が前後から等しいかどうかを見つける必要があります。

イラスト

最初と最後のノードは同じ値を持ち、2 番目と最後から 2 番目のノードは同じ値を持ち、以下同様に、前後からの距離が等しい各ノードは同じ値を持つことがわかります。

イラスト

ここで、最初と 2 番目のノードはそれぞれ最後と最後から 2 番目のノードに等しいですが、それ以降のノードは同じ値を持ちません。

スタックの使用

このメソッドでは、最初にこのクラスを使用してリンク リストを作成し、次にリンク リストにデータを追加し、リンク リストに存在するデータを出力するためのいくつかの基本関数を定義します。

時間と空間の複雑さ

上記のコードの時間計算量は O(N) です。ここで、N はリンク リストの長さです。

スタック データ構造を使用して要素を格納しているため、上記のコードの空間複雑さは O(N) です。

再帰を使用する

このメソッドでは、まず指定されたリンク リストの長さを見つけてから、再帰を使用してリンク リストの中央まで移動します。指定されたリンク リストの長さが奇数の場合は、中間ノードの次を返します。それ以外の場合は、中間ノードを返し、呼び出しごとに、再帰呼び出しから後ろから対応するノードを取得します。

このチュートリアルでは、指定されたリンク リスト ノードに回文内の値が含まれているかどうかを確認する JavaScript プログラムを実装しました。スタックと再帰を使用して 2 つのコードを実装しました。スタックの時間計算量は O(N)、空間計算量は O(N)、再帰メソッドの空間計算量は O(1) (再帰呼び出しデータが考慮しない）。

以上が単一リンクリストが回文であるかどうかをチェックする JavaScript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。