合并k个升序链表

题目描述：

给定k个升序排列的链表，将其合并为一个升序链表并返回头节点。
1

样例：

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
1
2
3
4
5
6
7
8
9
10

算法思路：

类似于 leetcode21 合并两个升序链表。 仍然是比较各个链表头节点的值，将值最小的节点放在合并后的链表后面。

为了更快的找到k个头节点中值最小的那个节点，可以使用小根堆来保存k个头节点，每次取出堆顶元素插入合并后的链表中，然后将下一个节点加入堆中。

时间复杂度：

由于使用堆维护链表最小值的节点，堆的插入是O(logk)的，所以总的时间复杂度是O(nlogk)。

空间复杂度：

使用了堆所以空间复杂度为O(n)

代码实现：

class Solution {
public:

    struct cmp{
        bool operator()(ListNode* l1, ListNode* l2){
            return l1->val > l2->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
        auto dummy = new ListNode(-1), tail = dummy;

        for(auto l:lists){
            if(l)   heap.push(l);
        }

        while(heap.size()){
            auto p = heap.top();
            heap.pop();
            tail = tail->next = p;
            if(p->next) heap.push(p->next);
        }

        return dummy->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

其中，实现小根堆的方法是重载 < 号。

leetcode 21 合并两个升序链表

题目描述：

给定两个升序链表，要求合并这两个链表并返回合并后链表的头节点。
1

样例：

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
1
2

算法思路：

使用两个链表的头节点，比较两个节点值的大小，将值小的先插入合并后的链表中，由于链表的头节点会被改变，所以使用虚拟头节点简化代码。

时间复杂度：

O(n)

空间复杂度：

O(1)

代码实现：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1), tail = dummy;
        while(l1 && l2){
            if(l1->val <= l2->val){
                tail = tail->next = l1;
                l1 = l1->next;
            }
            else{
                tail = tail->next = l2;
                l2 = l2->next;
            }
        }
        if(l1)  tail->next = l1;
        if(l2)  tail->next = l2;
        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19