Task

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

Example

1
2
3
4
5
6
7
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution

优先队列

  • 如图 leetcode23_1
  • 建立长度为k的优先队列,其中存放链表的节点们,初始化为每个链表的首元素
  • 每次从优先队列中弹出最小节点(需自定义节点的序),并将该最小节点的next(若非空)放入优先队列
  • 优先队列为空时结束
  • 这样能work的理由是:优先队列维护一个边界,该边界将链表们排成的“矩阵”(不一定是矩阵,每行长度各不相同)分成左右两侧,并能保证优先队列队首元素一定小于边界右侧的所有元素
  • 时间复杂度:队列长为k故每次插入的时间复杂度是O(logk),每个节点插入一次,总时间复杂度是O(nklog(k))
  • 空间复杂度:队列长度为k,空间复杂度是O(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
// Runtime: 32 ms, faster than 85.70% of C++ online submissions for Merge k Sorted Lists.
// Memory Usage: 12 MB, less than 13.09% of C++ online submissions for Merge k Sorted Lists.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //建立dummy节点处理初始情况
        ListNode *dummy=new ListNode;
        ListNode *tail=dummy;
        //定义序,类似operator<,由于priority_queue是大者优先,故需要小者优先时应逆转序,实现operator>
        auto order=[](ListNode *lhs,ListNode *rhs){return lhs->val>rhs->val;};
        //定义优先队列
        priority_queue<ListNode *,vector<ListNode *>,decltype(order)> q(order);
        //初始时将每个链表的首节点(若非空)存入优先队列
        for(auto node:lists)
            if(node) q.push(node);
        //队列为空则处理完
        while(!q.empty()){
            //取优先队列中最小节点挂在输出链表末尾
            tail->next=q.top(); q.pop();
            tail=tail->next;
            //将刚取出的最小节点的next(若非空)放入优先队列
            if(tail->next) q.push(tail->next);
        }
        return dummy->next;
    }
};

分治法

  • 将所有链表排序的问题分解为两个链表排序,如图 leetcode23_2
  • 时间复杂度:两个链表排序是O(n),归并排序的复杂度是O(klog(k)),故总时间复杂度O(nklog(k))
  • 空间复杂度:两个链表排序是O(1),递归栈的深度是O(log(k)),故总空间复杂度O(log(k))
  • 实现(两个链表排序的函数mergeTwoLists直接使用Leetcode21):
 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
40
41
42
43
44
45
46
47
48
49
50
// Runtime: 20 ms, faster than 99.00% of C++ online submissions for Merge k Sorted Lists.
// Memory Usage: 21.8 MB, less than 5.95% of C++ online submissions for Merge k Sorted Lists.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //处理输入为空的情形
        if(lists.empty()) return nullptr;
        return merge(lists,0,lists.size()-1);
    }
    //递归实现分治
    ListNode *merge(vector<ListNode *> &lists,int l,int r){
        //若刚好可分解为两链表排序,则调用mergeTwoLists处理
        if(l-r==1) return mergeTwoLists(lists[l],lists[r]);
        //若只有一个链表,直接返回
        if(l==r) return lists[l];
        //分治
        int m=(l+r)/2;
        ListNode *list1=merge(lists,l,m);
        ListNode *list2=merge(lists,m+1,r);
        return mergeTwoLists(list1,list2);
    }
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //建立dummy节点和添加结果用的tail指针
        ListNode *dummy=new ListNode;
        ListNode *tail=dummy;
        //当两个链表都未走到头时,比较两个节点
        while(l1 && l2){
            //保证l1节点比l2节点小
            if(l1->val > l2->val) swap(l1,l2);
            //将更小的节点放入结果链表中,继续走
            tail->next=l1;
            tail=tail->next;
            l1=l1->next;
        }
        //循环终止时可能有一个链表尾部非空,直接放到结果后面
        tail->next=l1?l1:l2;
        return dummy->next;
    }
};