合并K个排序链表

QUESTION:

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

示例:

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

EXPLANATION:

思路的话比较简单，就是一个一个的去找到对应的最小值然后添加，将最小值往后移动一位。直到整个列表都为null。
逻辑：
1.进入死循环
2.假设一个index为-1的最大值来进行锚点
3.循环遍历数组，获取到最小值
4.如果没有最小值则说明是null，则可以返回
5.获得最小值添加到结果链表中，并将对应的index往后后移一步
6.循环3-5直到跳出循环

这样的时间复杂度是数组长度n乘以链表最长m也就是n*m。我看了下结果中提供的最快的方式是采用的归并算法的思想，这样可以达到Nlogn的时间复杂度。

SOLUTION:

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null|| lists.length==0) return null;
        ListNode tmp = new ListNode(0);
        ListNode head = tmp;
        while (true){
            int min = -1;
            int minVal = Integer.MAX_VALUE;
            for(int i = 0;i<lists.length;i++){
                ListNode node =  lists[i];
                if(node!=null){
                    if(node.val<minVal){
                        min = i;
                        minVal = node.val;
                    }
                }
            }
            if(min==-1) break;
            ListNode nNode = new ListNode(minVal);
            tmp.next = nNode;
            tmp = tmp.next;
            lists[min] = lists[min].next;
        }
        return head.next;
    }
}
>
--> return <--