question:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

Ideas:

//链表
   public static ListNode mergeKLists(ListNode[] lists){
        if(lists==null || lists.length<1)
            return null;
        ListNode head = new ListNode(-1);
        ListNode phead =head;
        int count=0,index=0,min;    //奇数已经遍历完的链表
        while(count<lists.length){
            //找出K个链表的头结点值最小的那一个
            count=0;
            min = Integer.MAX_VALUE;
            for(int i=0;i<lists.length;i++){
                if(lists[i]==null){
                    count++;
                    continue;
                }
                if(lists[i].val<min){
                    min = lists[i].val;
                    index=i;
                }
            }
            if(count==lists.length)
                break;
            phead.next=lists[index];
            phead=phead.next;
            lists[index]=lists[index].next;
        }
        return head.next;
    }

方案二

//优先队列
  public static ListNode mergeKLists2(ListNode[] lists){

        ListNode head = new ListNode(-1);
        ListNode phead = head;
        //构造优先队列
        Queue<ListNode> minheap = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                if(o1.val<o2.val)
                    return -1;
                else if(o1.val==o2.val)
                    return 0;
                else {
                    return 1;
                }
            }
        }); //初始化优先队列
        for(ListNode l:lists){
            if(l!=null)
                minheap.add(l);
        }
        while(!minheap.isEmpty()){
            phead.next=minheap.poll();  //队列的头元素必为所有链表头元素中的最小值
            phead=phead.next;
            if(phead.next!=null)
                minheap.add(phead.next);
        }
        return head.next;
    }

方案三

//归并类似
    public static ListNode mergeKLists3(ListNode[] lists){

        int length=lists.length;
        int inteval=1;
        while(inteval<length){
            for(int i=0;i<length-inteval;i+=inteval*2){
                lists[i] = mergeTwoLists(lists[i],lists[i+inteval]);
            }
            inteval *=2;
        }
        return lists[0];
    }