My Java Solution with a PriorityQueue and Comparator - with comments


  • 1
    A
    public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // edge case - empty list
        ListNode nodes = null;
        if(lists.length == 0){
            return nodes;
        }
        // edge case - single entry in list
        if(lists.length==1){
            return lists[0];
        }
        
        //merge k-sorted linked lists - use priority queue
        Comparator<ListNode> lnvc = new ListNodeValueComparator();
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(lists.length, lnvc);
        
        for(ListNode listNode: lists){
            //add a list node to a priority queue.
            if(listNode !=null){
                priorityQueue.offer(listNode); //adds to the priority queue
            }
        }
        
        ListNode head = null;
        while(priorityQueue.size()>0){
            //poll() element from Queue
            ListNode smallestNow = priorityQueue.poll();
            if(smallestNow.next!=null){ // if linked list is not empty, offer next node to the heap
                priorityQueue.offer(smallestNow.next);
                smallestNow.next = null;
            }
            
            //get smallest node from list
            if(nodes == null){
                nodes = smallestNow;
                //head becomes the first smallest element
                head = smallestNow; 
            } else {
                nodes.next = smallestNow;
                nodes = nodes.next;
            }
        }
        
        return head;
    }
    //declare a custom comparator
    private class ListNodeValueComparator implements Comparator<ListNode>{
        
        /**
         * Compare ListNode
         **/
         @Override
         public int compare(ListNode listNode1, ListNode listNode2){
            //compares integer values of both nodes 
            return Integer.compare(listNode1.val, listNode2.val);   
         }
        
        
    } 
    

    }


  • 0
    J

    May I ask why we need to override the comparator in priorityqueue here? Because priorityqueue will pop out the least element by default.


Log in to reply
 

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