合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
解题思路

合并k个有序链表 (1).jpg

实现代码

public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        //k为链表个数
        int k = lists.length;
        while(k > 1){
            //将第一个和倒数第一个合并，第二个和倒数第二个合并，依次类推。
            for(int i = 0; i<k/2; i++){
                lists[i] = mergeTwoListNode(lists[i],lists[k-1-i]);
            }
            //合并之后，链表长度变为(k+1)/2。
            k = (k+1)/2;
        }
        return lists[0];
    }

    /**
     * 合并两个有序链表
     * @param node1
     * @param node2
     * @return
     */
    public ListNode mergeTwoListNode(ListNode node1,ListNode node2){
        ListNode head = new ListNode(-1);
        ListNode p = head;
        while(node1 != null && node2 != null){
            if(node1.val < node2.val){
                p.next = node1;
                node1 = node1.next;
            }else{
                p.next = node2;
                node2 = node2.next;
            }
            p = p.next;
        }
        if(node1 != null){
            p.next = node1;
        }
        if(node2 != null){
            p.next = node2;
        }
        return head.next;
    }