Untitled

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class MergeKSortedLists {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
        
        // Add all the heads of the lists to the priority queue
        for (ListNode node : lists) {
            if (node != null) {
                pq.add(node);
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        
        while (!pq.isEmpty()) {
            // Remove the smallest node from the priority queue
            ListNode smallest = pq.poll();
            tail.next = smallest;
            tail = smallest; // Move tail to the inserted node
            
            // Add the next node of the extracted node to the priority queue
            if (smallest.next != null) {
                pq.add(smallest.next);
            }
        }
        
        return dummy.next;
    }
    
    // Helper method to create a linked list from array
    public ListNode createList(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int value : array) {
            current.next = new ListNode(value);
            current = current.next;
        }
        return dummy.next;
    }

    // Helper method to print the linked list
    public void printList(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) {
        MergeKSortedLists solution = new MergeKSortedLists();
        
        // Example input as arrays
        int[] arr1 = {1, 4, 5};
        int[] arr2 = {1, 3, 4};
        int[] arr3 = {2, 6};
        
        // Create linked lists from arrays
        ListNode l1 = solution.createList(arr1);
        ListNode l2 = solution.createList(arr2);
        ListNode l3 = solution.createList(arr3);
        
        // Merge k sorted lists
        ListNode[] lists = {l1, l2, l3};
        ListNode mergedList = solution.mergeKLists(lists);
        
        // Print the merged list
        solution.printList(mergedList);
    }
}