Deloitte | COGNIZANT | IBM | CAPGEMINI
import java.util.PriorityQueue;
import java.util.Scanner;
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class Main {
public static ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode list : lists) {
if (list != null) {
minHeap.add(list);
}
}
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (!minHeap.isEmpty()) {
ListNode smallest = minHeap.poll();
current.next = smallest;
current = current.next;
if (smallest.next != null) {
minHeap.add(smallest.next);
}
}
return dummy.next;
}
public static ListNode arrayToLinkedList(int[] arr) {
if (arr.length == 0) return null;
ListNode head = new ListNode(arr[0]);
ListNode current = head;
for (int i = 1; i < arr.length; i++) {
current.next = new ListNode(arr[i]);
current = current.next;
}
return head;
}
public static void printLinkedList(ListNode head) {
ListNode current = head;
while (current != null) {
System.out.print(current.val + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int k = scanner.nextInt(); // Number of linked lists
ListNode[] lists = new ListNode[k];
scanner.nextLine(); // Move to next line
for (int i = 0; i < k; i++) {
String[] elements = scanner.nextLine().split(" ");
int[] arr = new int[elements.length];
for (int j = 0; j < elements.length; j++) {
arr[j] = Integer.parseInt(elements[j]);
}
lists[i] = arrayToLinkedList(arr);
}
ListNode mergedHead = mergeKLists(lists);
printLinkedList(mergedHead);
scanner.close();
}
}
#MERGE_K_SORTED_ARRAYS
#L&T
744 ·