Hợp nhất K danh sách liên kết được sắp xếp trong Java

Chúng ta được cung cấp K số danh sách liên kết có kích thước thay đổi được sắp xếp theo trình tự của chúng và chúng ta phải hợp nhất danh sách thành một danh sách kết quả theo cách mà mảng kết quả được sắp xếp nhỏ hơn và mảng kết quả được in dưới dạng đầu ra người dùng.

Hãy cho chúng tôi hiểu với ví dụ:-

Đầu vào -

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);

Đầu ra −Danh sách hợp nhất là ->

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

Giải thích −Chúng ta có K số danh sách liên kết được sắp xếp theo thứ tự. Quá trình hợp nhất bao gồm so sánh phần đầu của danh sách được liên kết bằng cách sử dụng hàm so sánh java và hợp nhất chúng với nhau trong mảng kết quả.

Đầu vào -

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);

Đầu ra - Danh sách hợp nhất là ->

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

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Chúng tôi nhập với số lượng danh sách (K) được yêu cầu để hợp nhất.
Một lớp nút được khởi tạo chịu trách nhiệm tạo các nút của danh sách được liên kết.
Sau đó, các nút của danh sách liên kết được khởi tạo theo thứ tự đã sắp xếp và phần đầu của danh sách được liên kết được chuyển qua hàm (mergeLists) với các tham số là k
Bên trong hàm, một vòng lặp được lặp lại từ danh sách thứ hai trở đi bên trong vòng lặp, một vòng lặp khác được lặp lại chứa tất cả tiện ích cho việc so sánh phần tử.
Đầu của cả danh sách thứ nhất và thứ i đều được thu thập và lưu trữ trong các biến.
Sau đó, cả hai phần đầu được kiểm tra để tìm phần tử đầu nhỏ hơn và kết quả và phần đầu kết quả sau đó được đặt làm phần đầu của danh sách cuối cùng.
Quá trình tương tự sau đó được thực hiện cho các phần tử sau của danh sách và dữ liệu được so sánh và lưu trữ theo đúng thứ tự của chúng.
Nếu danh sách được lặp lại đến cuối thì nút cuối cùng được đặt thành null và danh sách cuối cùng được trả lại cho người dùng dưới dạng đầu ra.

Ví dụ

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");
   }
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

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