Java solution with explanation using priority queue


  • 0
    L

    The priority queue is used to solve the problem. As for the priority, it is very important to know how to
    set up the comparator.

    PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
    
        queue.add(2);
        queue.add(3);
        queue.add(1);
    
    while(!queue.isEmpty()){
         System.out.print(queue.poll()+ ",");
    }
    
    // The result above is 1,2,3;
    

    The default order is ascending order.

    1. As for number the smallest will be at the head;
    2. As for string it is sorted alphabeticallyï¼›
    3. Also can be sorted based on the comparator.
      In this problem, the object is the node, we have to set up
      what to use to compare different nodes. Below shows a brief example to show how to set up a comparator.

    As the code shows, we have to set up a comparator;

    Comparator cmp;
    cmp = new Comparator(){
        public int compare(ListNode o1, ListNode l2){
             @Override
              return o1-o2;// the nodes will be in ascending order;
    //          return o2-o1 // the nodes will be in descending order;
        }
    };
    
    
    PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.length, cmp); 
    // don't worry about the lists.length, you can also set up to 1 if you like, 
    // as you add more nodes in the queue, the size will be enlarged as well. 
    

    The left part will be easy to understand, put all the head of each list into the priority, poll() the smallest and add its next if its next exists.

    Correct me if I am wrong. Thx!!!!

    
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists == null || lists.length ==0) return null;
    
            Comparator<ListNode> cmp = new Comparator<ListNode>(){
                @Override
                public int compare(ListNode o1, ListNode o2){
                    return o1.val-o2.val;
                }
            };
            PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.length, cmp);
    
            
            
            
            ListNode dummy = new ListNode(0);
            ListNode head = dummy;
            
            for(ListNode nodes : lists){
                if(nodes != null){
                    queue.add(nodes);
                }
            }
            while(!queue.isEmpty()){
                head.next = queue.poll();
                head= head.next;
                if(head.next != null){
                    queue.add(head.next);
                }
            }
            return dummy.next;
        }
    }
    
    

Log in to reply
 

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