合并K个有序链表

题目:合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

思路:

把每个链表得头放进小根堆里,这样每次取得都是全部链表得最小值,同时每次取出来一个结点后如果这个结点后面还有结点就继续放进去.

如下图,每次取出来一个值,链表向上移动

代码:

    public ListNode mergeKLists(ListNode[] lists) {
   if (lists==null||lists.length==0){
            return null;
        }
        //造个小根堆,以链表头结点得值排序得小根堆
        PriorityQueue<ListNode> MinHeap=new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });

        for (ListNode head: lists ){
            if (head==null){
                continue;
            }
            MinHeap.add(head);
        }
        ListNode head=new ListNode(1);
        ListNode curr=head;
        while (!MinHeap.isEmpty())
        {
            ListNode out=MinHeap.poll();
            curr.next=out;
            curr=curr.next;
            if (out.next!=null){
                MinHeap.add(out.next);
            }
        }
        return head.next;
    }