LeetCode 23. 合并K个排序链表

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

使用ArrayList发现可以，就是感觉效率不是很好。当然，使用优先队列效率也不是很好.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length , sz = 0;
        ArrayList<Integer> arrayList = new ArrayList<Integer>();

        for(int i=0;i<n;i++){
            ListNode listNode = lists[i];
            while(listNode !=null){
                arrayList.add(listNode.val);
                listNode = listNode.next;
            }
        }

        Collections.sort(arrayList);
        int index = 0;
        ListNode result = new ListNode(arrayList.get(0));
        ListNode pre = result;
        while(++index < arrayList.size()){
            pre.next = new ListNode(arrayList.get(index));
            pre = pre.next;
        }

        return result;
    }
}

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length ;
        if(lists == null || n ==0) return null;
        Queue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if( o1 > o2 ) return 1;
                else if( o1 < o2 ) return -1;
                return 0;
            }
        });

        for(ListNode list : lists){
            ListNode listNode = list;
            while(listNode != null){
                queue.add(listNode.val);
                listNode = listNode.next;
            }
        }

        ListNode result = null , pre = null;
        if(queue.isEmpty()) return null;
        result = new ListNode(queue.poll());
        pre = result;

        while(!queue.isEmpty()){
            pre.next = new ListNode(queue.poll());
            pre = pre.next;
        }

        return result;
    }
}

执行结果

还有一种方法就是利用归并排序的思想（一开始不知道为啥可以使用归并排序，后来发现这里的链表竟然是有序的）

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length ;
        if(lists == null || n ==0) return null;
        mergeSort(lists,0,n-1);
        return lists[0];
    }

    private void mergeSort(ListNode[] lists,int start,int end){
        if(start < end){
            int mid = (start+end)/2;

            mergeSort(lists,start,mid);
            mergeSort(lists,mid+1,end);

            merge(lists,start,mid+1);
        }
    }

    private void merge(ListNode[] lists,int s1,int s2){
        if(s1 >= s2 ) return ;
        if( lists[s1] == null ) lists[s1] = lists[s2];
        else{
            ListNode result = new ListNode(0),pre = result;
            ListNode p1 = lists[s1],p2 = lists[s2];
            while(p1!=null && p2!=null){
                if(p1.val < p2.val){
                    pre.next = p1;
                    pre = p1;
                    p1 = p1.next;
                }
                else{
                    pre.next = p2;
                    pre = p2;
                    p2 = p2.next;
                }
            }

            if(p1 != null) pre.next = p1;
            if(p2 != null) pre.next = p2;
            lists[s1] = result.next;
        }
    }

}

运行结果