Leetcode(23) Merge k Sorted Lists

发表于 | 更新于 | 分类于

Description:

Merge _k_ sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

解法：

利用了最小堆这种数据结构，我们首先把k个链表的首元素都加入最小堆中，它们会自动排好序。然后我们每次取出最小的那个元素加入我们最终结果的链表中，然后把取出元素的下一个元素再加入堆中，下次仍从堆中取出最小的元素做相同的操作，以此类推，直到堆中没有元素了，此时k个链表也合并为了一个链表，返回首节点即可，代码如下：

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
37
38
39
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode a, ListNode b) {
                return a.val - b.val;
            }
        });
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                q.offer(lists[i]);
            }
        }
        ListNode res = null;
        ListNode tail = null;
        while (!q.isEmpty()) {
            ListNode tmp = q.poll();
            if (res == null) {
                res = tmp;
                tail = tmp;
            } else {
                tail.next = tmp;
                tail = tmp;
            }
            if (tmp.next != null) {
                q.offer(tmp.next);
            }
        }
        return res;
    }
}