Java priority queue . Damn simple. with comment


  • 1
    Z
    /**
     * Use PriorityQueue to sort.
     * O(n*logk)
     */
    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            // make a heap and insert head of each list
            PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comp());
            for(ListNode n: lists){
                if(n != null)
                    heap.add(n);
            }
            
            // the head element to return, with min value
            ListNode head = heap.peek();
            
            while(!heap.isEmpty())    {
                ListNode min = heap.poll();
                if(min.next != null)
                    heap.add(min.next);
                
                min.next = heap.peek(); // peek return null on empty, sets null to tail
            }
            
            return head;
        }
        
        static class Comp implements Comparator<ListNode>{
            public int compare(ListNode left, ListNode right){
                return left.val - right.val;
            }
        }
    }

Log in to reply
 

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