LeetCode题解-23. 合并K个排序链表

发表于 更新于 分类于

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:

[
1->4->5,

1->3->4,

2->6
]

输出: 1->1->2->3->4->4->5->6

思路

最简单的就是用暴力解法，先把k个链表的所有元素取出来放进集合，然后对集合进行排序，排序后再从集合中取出来元素构造链表。

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static ListNode mergeKLists(ListNode[] lists) {
        ArrayList<Integer> numbers = new ArrayList<>();
        for (ListNode node : lists) {
            while (node != null) {
                numbers.add(node.val);
                node = node.next;
            }
        }
        Collections.sort(numbers);
        ListNode dummy = new ListNode(-1);
        ListNode nHead = dummy;
        for (int i : numbers) {
            dummy.next = new ListNode(i);
            dummy = dummy.next;
        }
        return nHead.next;
    }

优先队列

使用优先队列排序，直接获取头节点最小的链表的头节点。

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
public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        Queue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (ListNode node : lists) {
            if (node != null) {
                queue.add(node);
            }
        }
        ListNode dummy = new ListNode(-1);
        ListNode nHead = dummy;
        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            dummy.next = new ListNode(node.val);
            dummy = dummy.next;
            if (node.next != null) {
                queue.add(node.next);
            }
        }
        return nHead.next;
    }