合并K个有序链表

123. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

暴力

class Solution {
    List<Integer> list = new ArrayList<>();
    public ListNode mergeKLists(ListNode[] lists) {
        
        for(ListNode head : lists){
            ListNode p = head;
            while(p != null){
                list.add(p.val);
                p = p.next;
            }
        }

        Collections.sort(list);
        ListNode dummy = new ListNode();
        ListNode pre = dummy;
        for(Integer x : list){
            pre.next = new ListNode(x);
            pre = pre.next;
        }
        return dummy.next;
        
    }
}

分治递归合并

依次将链表数组的头和尾的链表两两归并，然后新链表保存到头部

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if(len == 0){
            return null;
        }
        if(len == 1){
            return lists[0];
        }

        for(int i = 0; i < len/2; i++){
            lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]);
        }
        ListNode[] newlists;
        if(len % 2 == 1){
            newlists = Arrays.copyOf(lists, len / 2 + 1);
        }else{
            newlists = Arrays.copyOf(lists, len / 2);
        }
        return mergeKLists(newlists);

    }

    //有序链表归并
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p1 = list1;
        ListNode p2 = list2;
        ListNode head = new ListNode();
        ListNode pre = head;
        while(p1 != null && p2 != null){
            if(p1.val <= p2.val){ //小的加入到新链
                pre.next = p1;
                p1 = p1.next;
            }else{
                pre.next = p2;
                p2 = p2.next;
            }
            pre = pre.next; //pre指向链尾
        }
        if(p1 != null){
            pre.next = p1;
        }
        if(p2 != null){
            pre.next = p2;
        }
        return head.next;
    }
}