题目

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

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

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

题解

我的解法质朴而纯真，保证一看就明白了，时间复杂度25%，只能说，凑合用~

和上一个类似的题目解法一致，先把lists里的所有节点都存到一个list里，然后用Collections.sort()排序，然后再连在一块，就是这么朴实无华。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<ListNode> res = new ArrayList<>();
        for (ListNode list : lists) {
            while (list != null) {
                res.add(new ListNode(list.val));
                list = list.next;
            }
        }
        Collections.sort(res, (p1, p2) -> p1.val - p2.val);
        ListNode ans = new ListNode();
        ListNode ansIndex = ans;
        while (!res.isEmpty()){
            ansIndex.next = res.removeFirst();
            ansIndex = ansIndex.next;
        }
        return ans.next;
    }
}