LeetCode刷题【23】合并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

JAVA 分治归并 其实挺简单的

1. 对于K个链表，可以两两合并（有点归并排序的意思）
2. 一次合并完了之后此时变成K/2个链表了，对剩下的链表继续两两合并
3. 最终全都合并到了一个链表里
4. 至于两个链表的合并过程，直接参考剑指Offer25题，比较简单算链表基本题了吧，我之前写的题解双指针合并，不如找两串珠子自己比划比划
5. 至于如何选择两两的过程可以简单设计下

//对应为k个链表在入参数组中的下标
1 [0,1],[2,3],[4,5],[6,7],[8]
2 [0,2],[4,6],[8]
4 [0,4],[8]
8 [0,8]

- 第一次 `[0,1],[2,3],[4,5],[6,7]`互相合并，结果留在第一个链表位置， `[8]`单独拉下了没关系先留着
- 第二次 `[0,2],[4,6]` 互相合并，结果存在0 , 4 位置，8继续留着，`[8]`没关系
- 第三次 再次合并`[0,4]`，`[8]`继续留着
- 最后一次合并`[0,8]`结束收工

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 1){
            return lists[0];
        }
        if (lists.length == 0){
            return null;
        }
        int dis = 1;
        while (dis < lists.length){
            //1 [0,1],[2,3],[4,5],[6,7],[8]
            //2 [0,2],[4,6],[8]
            //4 [0,4],[8]
            //8 [0,8]
            for (int i = 0; i + dis < lists.length; i += dis*2) {
                //合并两个有序链表  剑指Offer25题
                lists[i] = mergeTwoLists(lists[i],lists[i+dis]);
                lists[i+dis] = null;
            }
            dis *=2;
        }
        return lists[0];
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        ListNode head = new ListNode();
        ListNode cur = head;
        while ( l1 != null || l2 != null ){
            if (l1 == null || l2 == null){
                cur.next = l1==null?l2:l1;
                break;
            }
            if (l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return head.next;
    }
}