Java: Merge k Sorted Lists

Thought Process

The idea lies in efficiently merging multiple sorted lists while maintaining optimal performance. We use a min-heap to always retrieve the smallest node available. First, we push the head nodes of all lists into the heap. Then, we repeatedly extract the smallest node, add it to our merged list, and push its next node into the heap if it exists. 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        
        if(lists.length==0)
            return null;

        PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b)->a.val-b.val);

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        // As Link List are non contiguous in manner. So, think like we have put first node (not whole list)
        // of every list in our Min Heap. Although, it's correct to visualize that every node has address
        // of it's subsequent nodes but we are keeping each and every node in the min heap and then taking the
        // lowest value node everytime.
        for(ListNode nod : lists){
            if(nod!=null)
                pq.offer(nod);
        }

        while(!pq.isEmpty()){

            tail.next = pq.poll();
            tail = tail.next;

            if(tail.next!=null)
                pq.offer(tail.next);

        }  
        return dummy.next;

    }
}

Code Complexity

Time Complexity: O(n log k)

Each of the 'n' nodes is processed once, with heap operations taking O(log k) time for 'k' lists.

Space Complexity: O(k)

The heap stores at most 'k' nodes at any time, where 'k' is the number of lists.

Code copied!