Javaで2つのソートされたリンクリストをシンプルかつ最適な方法でマージする

ソートされた 2 つのリンク リストをマージすることは、効率的に解決できる一般的な問題です。 Java を使用してこれを簡単かつ最適な方法で行う方法を次に示します。

手順:

1. ダミー ノードを作成する: ダミー ノードを使用すると、マージ プロセスが簡素化されます。このノードは、マージされたリストの開始点として機能します。
2. ノードの比較: 両方のリンク リストの現在のノードを比較します。小さい方のノードをマージされたリストにアタッチし、そのリストのポインタを前方に移動します。
3. 残りのノードの処理: 一方のリストが他方より先に枯渇した場合は、枯渇していないリストの残りのノードをマージされたリストに追加します。
4. マージされたリストを返す: マージされたリストは、ダミー ノードの隣のノードから始まります。

Javaの実装:

リーリー

説明：

1. ListNodeクラス:

   • リンクされたリスト内の各ノードを整数値 (val) と次のノードへのポインター (next) で表します。

2. mergeTwoLists メソッド:

   • ダミー ノード: ダミー ノード (ダミー) は、開始点を提供することでマージ プロセスを簡素化するために使用されます。
   • 比較ループ: 両方のリンク リストを調べて、現在のノードを比較します。小さいノードがマージされたリストに追加され、そのリストの次のノードに移動します。
   • 残りのノード: リストの 1 つが使い果たされた後、他のリストの残りの部分をマージされたリストに直接接続します。
   • 戻り: 最後に、結合されたリストはダミー ノードの隣のノードから始まります。

3. printListメソッド:

   このユーティリティ関数は、リンク リスト内のすべてのノードを出力して、簡単に視覚化できます。

4. メインメソッド:

   • 2 つの並べ替えられたリンク リストを作成します: たとえば、1 -> 3 -> 5と2 -> 4 -> 6.
   • リストを結合する: 結合されたリストは 1 -> になります。 2 -> 3 -> 4 -> 5 -> 6.
   • リストを印刷する: 結合の前後で効果を確認します。

複雑：

• 時間計算量: ( O(n + m) )、ここで ( n ) と ( m ) は 2 つのリンクされたリストの長さです。両方のリストの各ノードは 1 回だけ処理されます。
• 空間の複雑さ: ( O(1) )、いくつかのポインターを除いて追加の空間は使用されないため。

この方法は、2 つの並べ替えられたリンク リストをマージするのにシンプルかつ最適であり、効率的でクリーンなコードを保証します。

以上がJavaで2つのソートされたリンクリストをシンプルかつ最適な方法でマージするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。