priority queue solution, o(nlogk), newest version


  • 0
     public ListNode mergeKLists(ListNode[] lists) {
              if (lists==null||lists.length==0) return null;
            
            PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){
                @Override
                public int compare(ListNode o1,ListNode o2){
                    if (o1.val<o2.val)
                        return -1;
                    else if (o1.val==o2.val)
                        return 0;
                    else 
                        return 1;
                }
            });
            
            ListNode dummy = new ListNode(0);
            ListNode tail=dummy;
            
            for (ListNode node:lists)
                if (node!=null)
                    queue.add(node);
                
            while (!queue.isEmpty()){
                tail.next=queue.poll();
                tail=tail.next;
                
                if (tail.next!=null)
                    queue.add(tail.next);
            }
            return dummy.next;
        }
    
    
    
    

Log in to reply
 

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