题目

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

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

示例 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

题解

public ListNode mergeKLists(ListNode[] lists) {
    List<ListNode> list = new ArrayList<>(Arrays.asList(lists));
    // 合并两个有序链表
    BiFunction<ListNode, ListNode, ListNode> merge = (l1, l2) -> {
        ListNode node = new ListNode(0);
        ListNode cursor = node;
        while (null != l1 && null != l2) {
            if (l1.val > l2.val) {
                cursor.next = new ListNode(l2.val);
                l2 = l2.next;
            } else {
                cursor.next = new ListNode(l1.val);
                l1 = l1.next;
            }
            cursor = cursor.next;
        }

        // l1多余l2的部分
        while (null != l1) {
            cursor.next = new ListNode(l1.val);
            l1 = l1.next;
            cursor = cursor.next;
        }
        // l2多余l1的部分
        while (null != l2) {
            cursor.next = new ListNode(l2.val);
            l2 = l2.next;
            cursor = cursor.next;
        }

        return node.next;
    };


    // 合并链表集合 直到只剩一个链表
    while (list.size() > 1) {
        // 取出列表前两个链表合并
        ListNode l1 = list.remove(0);
        ListNode l2 = list.remove(0);
        list.add(merge.apply(l1, l2));
    }


    return list.isEmpty() ? null : list.get(0);
}

public ListNode mergeKLists2(ListNode[] lists) {
    ListNode head = new ListNode(0);
    ListNode cursor = head;
    // 使用缓存 数字及出现次数
    Map<Integer, Integer> cache = new HashMap<>(16);
    for (ListNode list : lists) {
        ListNode node = list;
        while (null != node) {
            // 累加数字出现次数
            cache.merge(node.val, 1, (o, n) -> o + n);
            node = node.next;
        }
    }

    // 遍历缓存由小到大构造链表
    for (Integer key : cache.keySet().stream().sorted().collect(Collectors.toList())) {
        for (int i = 0; i < cache.get(key); i++) {
            cursor.next = new ListNode(key);
            cursor = cursor.next;
        }
    }

    return head.next;
}