当前位置：首页 > news >正文

OJ题-合并K个已排序的链表

news 来源：原创 2024/9/20 9:27:19

描述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数 0≤n≤50000≤n≤5000，每个节点的val满足 ∣val∣<=1000∣val∣<=1000

要求：时间复杂度 O(nlogn)O(nlogn)

下面给出C++代码的两种方法：

方法1：使用优先队列（最小堆）

优先队列可以很方便地处理多个链表头节点的最小值，每次从 K 个链表中取出最小的节点，合并到结果链表中。

思路：

使用优先队列（最小堆）来存储每个链表的当前头节点。
每次从堆中取出最小值节点，并将它的下一个节点重新加入堆。

重复这个过程，直到所有链表都被合并。

#include <queue>
#include <vector>
#include <iostream>struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 比较器，用于优先队列
struct Compare {bool operator()(ListNode* a, ListNode* b) {return a->val > b->val;}
};class Solution {
public:ListNode* mergeKLists(std::vector<ListNode*>& lists) {// 使用优先队列（最小堆）std::priority_queue<ListNode*, std::vector<ListNode*>, Compare> minHeap;// 初始化：将每个链表的头节点加入优先队列for (auto node : lists) {if (node) {minHeap.push(node);}}// 哑节点，便于构建新链表ListNode* dummy = new ListNode(0);ListNode* cur = dummy;// 逐步从最小堆中取出最小的节点，并更新链表while (!minHeap.empty()) {// 取出最小值节点ListNode* minNode = minHeap.top();minHeap.pop();// 将最小节点接到新链表的末尾cur->next = minNode;cur = cur->next;// 如果最小节点的下一个节点不为空，将其加入堆中if (minNode->next) {minHeap.push(minNode->next);}}// 返回合并后的链表return dummy->next;}
};

分析：

1、优先队列的使用：

优先队列使用自定义比较器 Compare，使得最小的节点始终位于堆顶。
每次从堆顶取出最小的节点，并将它的 next 节点放入堆中。

2、时间复杂度：O(N log K)，其中 N 是所有链表节点的总数，K 是链表的个数。每次从优先队列取出最小元素的时间复杂度为 O(log K)，一共需要执行 N 次。

3、空间复杂度：O(K)，优先队列最多存储 K 个元素。

方法2：分治法

可以使用分治法逐步将 K 个链表两两合并，类似于归并排序的过程。每次两两合并直到只剩一个链表。

思路：

将 K 个链表分成两部分，分别合并。
不断递归分治，直到只剩下两个链表，将它们合并。

最终得到合并后的链表。

class Solution {
public:// 合并两个有序链表ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (!l1) return l2;if (!l2) return l1;if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}}// 分治法合并 K 个链表ListNode* mergeKLists(std::vector<ListNode*>& lists) {if (lists.empty()) return nullptr;return mergeKListsHelper(lists, 0, lists.size() - 1);}// 分治递归函数ListNode* mergeKListsHelper(std::vector<ListNode*>& lists, int left, int right) {if (left == right) return lists[left];int mid = left + (right - left) / 2;ListNode* l1 = mergeKListsHelper(lists, left, mid);ListNode* l2 = mergeKListsHelper(lists, mid + 1, right);return mergeTwoLists(l1, l2);}
};