leetcode刷题笔记-23-合并K个升序链表

题目

https://leetcode.cn/problems/merge-k-sorted-lists/description/

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：
输入：lists = []
输出：[]

示例 3：
输入：lists = [[]]
输出：[]

最简单的思路就是用一个数组记录所有链表，再用sort将这个数组重排序，最后连成一个完整的升序链表。

思路1

思路1是用小堆来处理。

因为给出的链表已经是升序的，所以最终的有序链表的头节点，一定是给定的链表中的其中一个的头节点。

那么第二个节点呢？可能是另外一个链表的头节点，也有可能是当前选中的这个链表的第二个节点。比如下面的例子，第一个节点是2，第二个节点并不是其他链表的头节点，而是这一个链表的第二个节点3。

1
2
3
10 - 23
5 - 6 
2 - 3 - 7

所以我们需要用小堆来维护最终的大小关系，首先是遍历给出的链表数组，将所有链表的头节点插入小堆，随后取出堆顶元素，链入最终链表，如果这个节点还有下一个节点，那么就将下一个节点也插入小堆。

这样才能保证最终的顺序性。

代码

注意，使用小堆需要用STD提供的priority_queue容器，并自己写一个仿函数来比较两个链表节点的大小。

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
/**
 * 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 {
	// 注意优先级队列的传参是一个仿函数类
    class MyCmp {
    public:
        bool operator()(ListNode* l, ListNode* r) {
            return l->val > r->val; // 小堆
        }
    };

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 用最小堆来实现，注意最小堆是大的往上题，cmp中是大于
        priority_queue<ListNode*, vector<ListNode*>, MyCmp> que;
        // 把不为空的链表头节点插入，因为链表本来都是升序的
        // 那么最终的有序链表的第一个节点肯定是某一个链表的头节点
        for (auto& i : lists) {
            if (i != nullptr) {
                que.push(i);
            }
        }
        // 新建一个烧饼节点
        ListNode* phead = new ListNode;
        ListNode* cur = phead;
        while (!que.empty()) {
            // 取出头节点
            ListNode* head = que.top();
            que.pop();
            // 如果有下一个节点，插入最小堆
            if (head->next != nullptr) {
                que.push(head->next);
            }
            // 将其连入链表
            cur->next = head;
            cur = cur->next;
        }
        return phead->next;
    }
};

image.png

思路2

方法2就是用之前写过的21.合并两个有序链表的练习。每次都选中两个链表进行合并，直到最终合并所有链表。

这里可以采用分治的思路，将链表数组拆分后进行合并。

代码

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
class Solution {
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode;
        ListNode* oldHead = head;
        ListNode *cur1 = list1, *cur2 = list2;
        while (cur1 != nullptr && cur2 != nullptr) {
            if (cur1->val >= cur2->val) {
                head->next = cur2;
                head = head->next;
                cur2 = cur2->next;
            } else {
                head->next = cur1;
                head = head->next;
                cur1 = cur1->next;
            }
        }

        if (cur1 == nullptr) {
            head->next = cur2;
        } else {
            head->next = cur1;
        }
        return oldHead->next;
    }
    // 合并从 lists[i] 到 lists[j-1] 的链表
    ListNode* mergeKLists(vector<ListNode*>& lists, int i, int j) {
        int m = j - i;
        if (m == 0) {
            return nullptr; // 注意输入的 lists 可能是空的
        }
        if (m == 1) {
            return lists[i]; // 无需合并，直接返回
        }
        auto left = mergeKLists(lists, i, i + m / 2);  // 合并左半部分
        auto right = mergeKLists(lists, i + m / 2, j); // 合并右半部分
        return mergeTwoLists(left, right); // 最后把左半和右半合并
    }

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergeKLists(lists, 0, lists.size());
    }
};