Simple priorityQueue based solution in java


  • 0

    This is a pretty standard k-way merge algorithm. Below is my basic implementation in java:

    public ListNode mergeKLists(ListNode[] lists) {
    
    	if (lists == null || lists.length == 0) return null;
    
    	PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>((a, b) -> a.val - b.val);
    	for (ListNode list : lists) {
    	   if (list != null) {
    		   pq.offer(list); // only add non-null elements into the pq
    	   }
    	}
    
    	ListNode dummy = new ListNode(0);
    	ListNode ptr = dummy;
    	// Loop over the pq and selectively add nodes
    	while (!pq.isEmpty()) {
    	   ListNode node = pq.poll();
               ptr.next = node;
    	   if (node != null && node.next != null) {
    		   // only add non-null elements into the pq
    		   pq.offer(node.next);
    	   }
    	   ptr = ptr.next;
    	}
    
    	ptr.next = null; // terminate list
    
    	return dummy.next;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.