Javaで連結リストを交互の位置にある別の連結リストにマージする方法

この記事では、2つの連結リスト(以下 List_1 および List_2)が与えられたとき、List_2 の要素を List_1 の交互の位置に挿入してマージする方法を解説します。List_1 に挿入しきれなかった要素は、「List_2 の残りの要素」として出力されます。

具体例

入力 −

List_1 =

List_2 =

出力 − マージ後のリスト:

説明 − 2つのリスト List_1 と List_2 が与えられています。List_2 の要素を可能な限り List_1 の交互の位置に挿入すると、マージ後の List_1 は 10→3→2→1→1→4→2→5→5 となり、List_2 には 7→2 が残ります。

入力 −

List_1 = 11 → 12 → 13

List_2 = 14 → 15 → 16 → 17 → 18

出力 − マージ後のリスト: 11 → 14 → 12 → 15 → 13 → 16

説明 − List_2 の要素を挿入できるだけ交互の位置に入れると、マージ後の List_1 は 11 → 14 → 12 → 15 → 13 → 16 となり、List_2 には 17 → 18 が残ります。

プログラムで使用しているアプローチ

• 連結リストの先頭ノードを指す head ノードを作成します。

• 連結リストを構築するための Node クラスを作成します。このクラスは value と next をデータメンバーとして持ち、デフォルトコンストラクタ Node(int val) を定義して、value に val を、next に NULL を設定します。

• add(int updated_value) メソッド内で、連結リストへ要素を追加します。

  • new_node オブジェクトを作成し、updated_value をコンストラクタに渡します。

  • new_node.next に現在の head を設定し、head を new_node に更新します。先頭への挿入になるため、リストは追加した順序と逆順に構築される点に注意してください。

• mergeList(TutorialPoint list) メソッド内で、2つのリストを交互にマージします。

  • n1_curr を head に、n2_curr を list.head に設定します。

  • n1_next と n2_next オブジェクトを作成します。

  • n1_curr != null かつ n2_curr != null である間 While ループを実行します。ループ内では、まず n1_next に n1_curr.next を、n2_next に n2_curr.next を保存しておき、その後 n2_curr.next に n1_next を、n1_curr.next に n2_curr をつなぎ替えます。最後に n1_curr を n1_next へ、n2_curr を n2_next へ進めます。

  • ループ終了後、list.head に n2_curr を設定することで、マージできなかった残りの要素を List_2 側に保持します。

• main() メソッド内で次の処理を行います。

  • TutorialPoint list_1 = new TutorialPoint() と TutorialPoint list_2 = new TutorialPoint() を作成します。

  • list_1.add(13)、list_1.add(12)、list_1.add(11) として list_1 に要素を追加します。

  • list_2.add(18)、list_2.add(17)、list_2.add(16)、list_2.add(15)、list_2.add(14) として list_2 に要素を追加します。

  • list_1.mergeList(list_2) を呼び出し、list_2 の要素を list_1 にマージします。

  • 最終的なリストを出力します。

サンプルコード

public class TutorialPoint{   Node head;   class Node{      int value;      Node next;      Node(int val){         value = val;         next = null;      }   }   void add(int updated_value){      Node new_node = new Node(updated_value);      new_node.next = head;      head = new_node;   }   void mergeList(TutorialPoint list){      Node n1_curr = head, n2_curr = list.head;      Node n1_next, n2_next;      while (n1_curr != null && n2_curr != null){         n1_next = n1_curr.next;         n2_next = n2_curr.next;         n2_curr.next = n1_next;         n1_curr.next = n2_curr;         n1_curr = n1_next;         n2_curr = n2_next;      }      list.head = n2_curr;   }   public static void main(String args[]){      TutorialPoint list_1 = new TutorialPoint();      TutorialPoint list_2 = new TutorialPoint();      list_1.add(13);      list_1.add(12);      list_1.add(11);      list_2.add(18);      list_2.add(17);      list_2.add(16);      list_2.add(15);      list_2.add(14);      list_1.mergeList(list_2);      System.out.println("Merged list is:");      Node temp = list_1.head;      while (temp != null){         System.out.print(temp.value + " ");         temp = temp.next;      }      System.out.println();   }}

出力

上記のコードを実行すると、次の出力が得られます。

Merged list is:
11 14 12 15 13 16

このアルゴリズムは、短い方のリストの長さを n とすると時間計算量 O(n) で動作し、必要な追加メモリはポインタ数個分のみのため、空間計算量は O(1) です。ノードの値を入れ替えるのではなく next ポインタをつなぎ替えるだけで実現できる点が、この手法の大きな特徴です。