हमें चर आकार की 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) के साथ इनपुट दिया गया है।
एक नोड वर्ग प्रारंभ किया जाता है जो लिंक्ड सूची के नोड्स बनाने के लिए जिम्मेदार है।
उसके बाद लिंक्ड सूची के नोड्स को क्रमबद्ध क्रम में प्रारंभ किया जाता है और लिंक्ड सूची के हेड को पैरामीटर के रूप में k के साथ फ़ंक्शन (mergeLists) के माध्यम से पास किया जाता है
फ़ंक्शन के अंदर दूसरी सूची से एक लूप दोहराया जाता है और लूप के अंदर एक और लूप दोहराया जाता है जिसमें तत्वों की तुलना के लिए सभी उपयोगिता शामिल होती है।
पहली और 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