জাভাতে 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টি ক্রমানুসারে সর্টেড লিংকড লিস্ট দেওয়া আছে। মার্জ প্রক্রিয়ায় জাভা কমপেয়েটর ফাংশন ব্যবহার করে লিংকড লিস্টের হেডগুলো তুলনা করে তাদের ফলাফল লিস্টে একসাথে মার্জ করা হয়।

উদাহরণ ২

ইনপুট:

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টি সর্টেড লিংকড লিস্ট মার্জ করা হয়।

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

• মার্জ করার জন্য লিস্টের সংখ্যা (K) ইনপুট হিসেবে নেওয়া হয়।
• Node ক্লাস ইনিশিয়ালাইজ করা হয় যা লিংকড লিস্টের নোড তৈরি করার জন্য দায়িত্বী।
• লিংকড লিস্টের নোডগুলো ক্রমанুসারে ইনিশিয়ালাইজ করা হয় এবং হেড mergeLists ফাংশনে k প্যারামিটারসহ পাস করা হয়।
• ফাংশনের ভিতরে দ্বিতীয় লিস্ট থেকে শুরু করে একটি লুপ ইটারেট করা হয়, যার ভিতরে উপাদানগুলো তুলনার জন্য একটি নেস্টেড লুপ থাকে।
• প্রথম এবং 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 priorityQueue; 
        priorityQueue = new PriorityQueue(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