Java priority queue version


  • 0
    public class Solution {
    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 n1, ListNode n2){
                return n1.val - n2.val;
            }
            });
            
        for(ListNode n : lists){
            if(n != null)
                queue.add(n);
        }
        ListNode head = new ListNode(0);
        ListNode n = head;
        while(!queue.isEmpty()){
            ListNode temp = queue.poll();
            n.next = temp;
            n = n.next;
            if(temp.next != null)
                queue.offer(temp.next);
        }
        return head.next;
    }
    

    }


  • 0
    Y

    priortyQueue use the heap sort ,so the time complexity is mn(Log(mn)) m represent the average number of element in list and the n represent the number of List

    this analysis is right?


Log in to reply
 

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