Accepted Simple Java soln based on Priority Queue


  • 0
    R
    public ListNode mergeKLists(ListNode[] lists) {
            ListNode res = null;
            if(lists.length == 0) return res;
            // Create a min Heap and put all the head node of all lists
            PriorityQueue<ListNode> heap = new PriorityQueue(new Comparator<ListNode>(){
                @Override
                public int compare(ListNode a, ListNode b){
                    return a.val - b.val;
                }
            });
            for(ListNode list : lists){
                if(list != null) heap.add(list);
            }
            ListNode x = null;
            // keep plucking out the min from heap, add it to the result and then put the next element
            // from the same list whose element was removed.
            while(!heap.isEmpty()){
                ListNode min = heap.remove();
                if(min.next != null) heap.add(min.next);
                if(res == null) {
                    x = new ListNode(min.val);
                    res = x;
                }
                else{
                    x.next = new ListNode(min.val);
                    x = x.next;
                }
            }
            return res;
        }
    

Log in to reply
 

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