Leetcode 23. 合并K个排序链表

发表于

题目

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

示例:

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

思路

这道题，一开始我是想按照归并排序（看到了合并两个字的第一反应）来做。结果，由于这个是K个链表的排序，要用归并排序很麻烦。（感觉需要一环套一环）

因此，直接参考了别人的思路来写。其实，最暴力的方法就是把所有的数放到一个数组里，然后排序，最坏时间复杂度为O(NlogN)。而由于k个链表是有序的，实际上我们只需要维护k个指针，从k个链表的头向尾移动。每次选取k个链表的表头里最小的一个加入有序链表里。在C++中，我们使用priority_queue来实现堆。一般默认为最大堆（less\），最小堆为(greater\)。

由于此题是要对指针进行排序，因此需要重载运算符。我们使用struct结构体来完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct cmp{
    bool operator()(ListNode* a, ListNode* b){
        return a->val > b.val;
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists){
    priority_queue<ListNode*, vector<ListNode*>, cmp> heapk; // 最小堆，输出堆中的最小元素
    for (auto p : lists){
        heapk.push(p);
    }
    ListNode *head = new ListNode(-1);
    ListNode *cur = head;
    while (!heapk.empty()){
        ListNode *temp = heapk.top();
        heapk.pop();
        cur->next = temp;
        cur = cur->next;
        if (temp->next) heapk.push(temp->next);
    }
    cur = head->next;
    delete head;
    return cur;
}