JavaでK個のソートされたリンクリストをマージする

順番に並べ替えられた可変サイズのリンクリストがK個与えられ、結果の配列が順番に並べ替えられ、結果の配列が出力として出力されるように、リストを結果のリストにマージする必要があります。ユーザー。

例を挙げて理解しましょう：-

入力 −

int k =3;

list [0] =new Node（11）;

list [0] .next =new Node（15）;

list [0] .next.next =new Node（17）;

list [1] =new Node（2）;

list [1] .next =new Node（3）;

list [1] .next.next =new Node（26）;

list [1] .next.next.next =new Node（39）;

list [2] =new Node（4）;

list [2] .next =new Node（8）;

list [2] .next.next =new Node（10）;

出力 -マージされたリストは->

2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> null

説明 −順番に並べ替えられたK個のリンクリストが表示されます。マージプロセスには、Javaコンパレータ関数を使用してリンクリストの先頭を比較し、それらを結果の配列にマージすることが含まれます。

入力 −

int k =2;

list [0] =new Node（1）;

list [0] .next =new Node（4）;

list [0] .next.next =new Node（5）;

list [1] =new Node（2）;

list [1] .next =new Node（3）;

list [1] .next.next =new Node（6）;

list [1] .next.next.next =new Node（8）;

出力 −マージされたリストは->

1>> 2>> 3>> 4>> 5>> 6>> 8>> null

説明 −順番に並べ替えられたK個のリンクリストが表示されます。マージプロセスには、Javaコンパレータ関数を使用してリンクリストの先頭を比較し、それらを結果の配列にマージすることが含まれます。

以下のプログラムで使用されるアプローチは次のとおりです-

• マージする必要のあるリスト（K）の数が入力されます。

• リンクリストのノードの作成を担当するノードクラスが初期化されます。

• その後、リンクリストのノードが並べ替えられた順序で初期化され、リンクリストの先頭がk

  としてパラメータを使用して関数（mergeLists）を通過します。

• 関数内では、ループが2番目のリストから繰り返され、ループ内で別のループが繰り返されます。このループには、要素の比較のためのすべてのユーティリティが含まれています。

• 最初のリストとi番目のリストの両方の先頭がキャプチャされ、変数に格納されます。

• 次に、両方のヘッドで小さいヘッド要素と結果がチェックされ、結果のヘッドが最終リストのヘッドとして設定されます。

• 次に、リストの次の要素に対して同様のプロセスが実行され、データが比較され、正しい順序に従って保存されます。

• リストが最後まで繰り返されると、最後のノードがnullに設定され、最後のリストが出力としてユーザーに返されます。

例

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
class Node {
   int data;
   Node next;
   public Node(int data) {
      this.data = data;
      this.next = null;
   }
}
public class testClass{
   public static Node mergeLists(Node[] list, int k) {
      PriorityQueue<Node> priorityQueue;
      priorityQueue = new PriorityQueue<Node>(Comparator.comparingInt(a ->((Node) a).data));
      priorityQueue.addAll(Arrays.asList(list).subList(0, k));
      Node head = null, last = null;
      while (!priorityQueue.isEmpty()) {
         Node min = priorityQueue.poll();
         if (head == null) {
            head = last = min;
         }
         else {
            last.next = min;
            last = min;
         }
         if (min.next != null) {
            priorityQueue.add(min.next);
         }
      }
      return head;
   }
   public static void main(String[] s) {
      int k = 3;
      Node[] list = new Node[k];
      list[0] = new Node(11);
      list[0].next = new Node(15);
      list[0].next.next = new Node(17);
      list[1] = new Node(2);
      list[1].next = new Node(3);
      list[1].next.next = new Node(26);
      list[1].next.next.next = new Node(39);
      list[2] = new Node(4);
      list[2].next = new Node(8);
      list[2].next.next = new Node(10);
      System.out.println("The merged list is-->");
      Node head = mergeLists(list, k);
      while (head != null) {
         System.out.print(head.data + ">> ");
         head = head.next;
      }
      System.out.print("null");
   }
}

出力

上記のコードを実行すると、次の出力が生成されます

The merged list is-->
2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> null