合并K个排序链表（困难）

---

题目叙述：

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

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

解题思路：

我们先从其中的一个子问题开始看，那就是如何合并两个有序链表，我们可以先取起始一个值比较小的哪一个链表，作为我们的最后答案的链表的头，然后我们，用两个引用一个h1指向比较小的哪一个链表，h2指向比较大的那个链表进行，使h1.next.val与h2.val值进行比较，为什么要这样做呢？这样可以避免h2经过头插插入，使插入的情况变得更简单。两个指针联动跑起来，直到h1.next==null||h2==null，如果h1.next==null说明h2还有元素没有跑完但是现在比h1中所有都大，直接插入到尾部就好了。实现代码在最后实现代码中有这里就不单拿出来了。
然后我们的题目是k个，这样我们想归并排序的思维将我们所有的链表进行两两一组合并，然后直到合成只剩下最后一条放在lists[0]上就是我们最后的结果，可以看出两个链表合并时间复杂度为：O(n)，归并的为O(logk)，所以最终的时间复杂度为O(nlogk)。空间复杂度为O(1) PS：这是第一篇LeetCode中的难度为困难的，如有更好的解法请多多指教。

实现代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length<1){
           return null;
        }
        int len=lists.length;
        if(len==1){
            return lists[0];
        }
        int cnt=0;
        while(len>1){
            int mid=len/2;
            for(int i=0;i<mid;i++){
                lists[i]=mergeTwoLists(lists[2*i],lists[2*i+1]);
            }
            len=(len+1)/2;
            if(len>mid){
                lists[mid]=lists[2*mid];
            }
        }
        return lists[0];
    }
    //合并两链表
    public ListNode mergeTwoLists(ListNode list1,ListNode list2){
        if(list1==null){
            return list2;
        }else if(list2==null){
            return list1;
        }
        ListNode h1,h2;
        if(list1.val<=list2.val){
            h1=list1;
            h2=list2;
        }else{
            h1=list2;
            h2=list1;
        }
        ListNode res=h1;
        while(h1.next!=null&&h2!=null){
            if(h2.val<h1.next.val){
                ListNode help=h2;
                h2=h2.next;
                help.next=h1.next;
                h1.next=help;
            }
            h1=h1.next;
        }
        if(h1.next==null){
            h1.next=h2;
        }
        return res;
    }
}