LeetCode23-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
要减小算法的复杂度，就要利用已知的条件，已知的条件就是已有的顺序。

public ListNode mergeKLists(ListNode[] lists) {    ListNode trueHead=new ListNode(0);    if(lists.length<=0) return trueHead.next;    trueHead.next=lists[0];    for(int i=1;i<lists.length;i++){        ListNode cur=lists[i];        ListNode pre=trueHead;        while(cur!=null){            while(pre.next!=null && pre.next.val<=cur.val) pre=pre.next;            ListNode next=pre.next;            ListNode curNext=cur.next;            pre.next=cur;            cur.next=next;            cur=curNext;            pre=pre.next;        }    }    return trueHead.next;}

我们一共会做k-1次合并，可以通过归并操作减少到logk次

public ListNode mergeKLists(ListNode[] lists) {        if(lists.length<=0) return null;        int len=1;        while(len<=lists.length){            for(int i=0;i<lists.length-len;i=i+2*len){                ListNode left=lists[i];                ListNode cur=lists[i+len];                ListNode trueHead=new ListNode(0);                trueHead.next=left;                ListNode pre=trueHead;                while(cur!=null){                    while(pre.next!=null && pre.next.val<=cur.val) pre=pre.next;                    ListNode next=pre.next;                    ListNode curNext=cur.next;                    pre.next=cur;                    cur.next=next;                    cur=curNext;                    pre=pre.next;                }                lists[i]=trueHead.next;            }            len*=2;        }        return lists[0];    }