(nk)log(k) Solution


  • 1
    P

    /**

    • Definition for singly-linked list.
    • public class ListNode {
    • int val;
      
    • ListNode next;
      
    • ListNode(int x) { val = x; }
      
    • }
      */

    class QueueListNode{
    public QueueListNode(ListNode listnode, int size){
    this.listNode = listnode;
    this.size = size;
    }

     ListNode listNode;
     int size;
    

    }

    public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

        if(lists == null || lists.length == 0)
            return null;
        
        if(lists.length ==1)
            return lists[0];
        
        PriorityQueue<QueueListNode> pqueue = new PriorityQueue<QueueListNode>(new Comparator<QueueListNode>(){
            public int compare(QueueListNode list1, QueueListNode list2){
                return list1.size - list2.size;
            }
        });
        
        for(int i=0; i<lists.length; i++){
            ListNode list = lists[i];
            if(list ==null)
                continue;
            ListNode temp = list;
            int size =0;
            while(temp!= null){
                size++;
                temp = temp.next;
            }
            pqueue.add(new QueueListNode(list,size));
        }
        if(pqueue.size() ==0)
            return null;
        
        while(pqueue.size()>1){
          QueueListNode queueNode1 = pqueue.remove();
          QueueListNode queueNode2 = pqueue.remove();
          pqueue.add(merge(queueNode1,queueNode2));
        }
        return pqueue.remove().listNode;
        
        
    }
    public QueueListNode merge(QueueListNode queueNode1, QueueListNode queueNode2){
        ListNode temp1 =queueNode1.listNode;
        ListNode temp2 =queueNode2.listNode;
        ListNode mergedNode;
        
        if(temp1.val <= temp2.val){
            mergedNode = temp1;
            temp1= temp1.next;
        }else{
            mergedNode = temp2;
            temp2= temp2.next;
        }
        ListNode temp3 = mergedNode;
        
        
        while(temp1!= null && temp2 != null){
            if(temp1.val <= temp2.val){
                temp3.next = temp1;
                temp1 = temp1.next;
            }else{
                temp3.next = temp2;
                temp2 = temp2.next;
                
            }
            temp3 = temp3.next;
        }
        if(temp1!=null){
            temp3.next = temp1;
        }else{
            temp3.next = temp2;
        }
        return new QueueListNode(mergedNode, queueNode1.size + queueNode2.size);
    }
    

    }


Log in to reply
 

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