LeetCode-23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

堆+链表 时间复杂度O(nlogk)

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(0);
        head.next = null;
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
            public int compare(ListNode n1,ListNode n2){
                return n1.val-n2.val;
            }
        } );
        for(int i = 0;i< lists.length;i++){
            if(lists[i]!=null){
                queue.add(lists[i]);
            }
        }
        ListNode cur = head;
        while(!queue.isEmpty()){
            ListNode tmp = queue.poll();
            cur.next = tmp;
            cur = cur.next;
            if(tmp.next!=null){
                queue.add(tmp.next);
            }
        }
        return head.next;
    }