জাভাতে K সাজানো লিঙ্ক তালিকা মার্জ করুন

আমাদেরকে ভেরিয়েবল সাইজের লিঙ্কযুক্ত তালিকার একটি K সংখ্যা দেওয়া হয়েছে যা তাদের ক্রম অনুসারে সাজানো হয়েছে এবং আমাদের তালিকাটিকে একটি ফলাফল তালিকায় এমনভাবে একত্রিত করতে হবে যাতে ফলাফলের অ্যারেটি ক্রমানুসারে সাজানো হয় এবং ফলাফলের অ্যারেটি আউটপুট হিসাবে মুদ্রিত হয় ব্যবহারকারী।

উদাহরণ দিয়ে বোঝা যাক:-

ইনপুট −

int k =3;

তালিকা[0] =নতুন নোড(11);

list[0].next =new Node(15);

তালিকা[0].next.next =নতুন নোড(17);

তালিকা[1] =নতুন নোড(2);

list[1].next =new Node(3);

তালিকা[1].next.next =নতুন নোড(26);

তালিকা[1].next.next.next =নতুন নোড(39);

তালিকা[2] =নতুন নোড(4);

list[2].next =new Node(8);

তালিকা[2].next.next =নতুন নোড(10);

আউটপুট -একত্রিত তালিকা হল-->

2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> শূন্য

ব্যাখ্যা −আমাদের K নম্বরের সাথে লিঙ্ক করা তালিকা দেওয়া হয়েছে যা ক্রমানুসারে সাজানো হয়েছে। একত্রীকরণ প্রক্রিয়ার মধ্যে রয়েছে জাভা তুলনাকারী ফাংশন ব্যবহার করে লিঙ্ক করা তালিকার প্রধানের তুলনা করা এবং ফলাফলের অ্যারেতে তাদের একত্রিত করা।

ইনপুট −

int k =2;

তালিকা[0] =নতুন নোড(1);

list[0].next =new Node(4);

তালিকা[0].next.next =নতুন নোড(5);

তালিকা[1] =নতুন নোড(2);

list[1].next =new Node(3);

তালিকা[1].next.next =নতুন নোড(6);

তালিকা[1].next.next.next =নতুন নোড(8);

আউটপুট - একত্রিত তালিকা হল-->

1>> 2>> 3>> 4>> 5>> 6>> 8>> শূন্য

নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি হল -

আমরা তালিকার সংখ্যা দিয়ে ইনপুট করছি(কে) যা একত্রিত করতে হবে।
একটি নোড ক্লাস শুরু করা হয় যা একটি লিঙ্ক করা তালিকার নোড তৈরির জন্য দায়ী৷
তারপরে লিঙ্ক করা তালিকার নোডগুলিকে সাজানো ক্রমানুসারে আরম্ভ করা হয় এবং লিঙ্ক করা তালিকার প্রধানটি ফাংশন (মার্জলিস্ট) এর মাধ্যমে k
পরামিতি সহ পাস করা হয়।
ফাংশনের ভিতরে একটি লুপ পুনরাবৃত্ত করা হয় দ্বিতীয় তালিকা থেকে লুপের ভিতরে আরেকটি লুপ পুনরাবৃত্তি করা হয় যাতে উপাদানটির তুলনার জন্য সমস্ত উপযোগিতা রয়েছে৷
প্রথম এবং প্রথম উভয় তালিকার প্রধান ক্যাপচার করা হয় এবং ভেরিয়েবলে সংরক্ষণ করা হয়।
উভয় হেড তারপর ছোট হেড এলিমেন্ট এবং ফলাফলের জন্য চেক করা হয় এবং ফলাফল হেড তারপর চূড়ান্ত তালিকার প্রধান হিসাবে সেট করা হয়।
অনুরূপ প্রক্রিয়া তারপর তালিকার নিম্নলিখিত উপাদানগুলির জন্য করা হয় এবং ডেটা তুলনা করা হয় এবং তাদের সঠিক ক্রম অনুসারে সংরক্ষণ করা হয়৷
যদি তালিকাটি শেষ পর্যন্ত পুনরাবৃত্তি করা হয় তবে শেষ নোডটি নাল সেট করা হয় এবং চূড়ান্ত তালিকাটি ব্যবহারকারীকে আউটপুট হিসাবে ফেরত দেওয়া হয়।

উদাহরণ

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