合并K个升序链表

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：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：

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

示例 3：

1
2
输入：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

方法一：遍历数组，两两合并lists[i-1]和lists[i]，将合并的结果放入lists[i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        int n = lists.length;
        for (int i = 1; i < lists.length; i++) {
            ListNode h = new ListNode();
            ListNode tail = h;
            ListNode list0 = lists[i - 1];
            ListNode list1 = lists[i];
            while (list0 != null && list1 != null) {
                if (list0.val < list1.val) {
                    tail.next = list0;
                    list0 = list0.next;
                } else {
                    tail.next = list1;
                    list1 = list1.next;
                }
                tail = tail.next;
            }
            tail.next = list0 != null ? list0 : list1;
            lists[i] = h.next;
        }
        return lists[n - 1];
    }
}

方法二：分治，类似归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        int mid = l + r >> 1;
        ListNode list1 = merge(lists, l, mid);
        ListNode list2 = merge(lists, mid + 1, r);
        return mergeTwo(list1, list2);
    }

    private ListNode mergeTwo(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();
        ListNode tail = head;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = list1 != null ? list1 : list2;
        return head.next;
    }
}