leetcode hot100-34 合并K个升序链表
方法一:分治法(相当于对暴力法的优化)
class Solution {
private:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummyhead = new ListNode(0);
ListNode* cur = dummyhead;
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1;
list1 = list1->next;
} else {
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2;
return dummyhead->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists, int i, int j) {
int m = j - i;
// 计算当前范围 [i, j) 之间的链表数量
if (m == 0) {
return nullptr; // 注意输入的 lists 可能是空的
}
if (m == 1) {
return lists[i]; // 无需合并,直接返回
}
ListNode* left = mergeKLists(lists, i, i + m / 2);
ListNode* right = mergeKLists(lists, i + m / 2, j);
return mergeTwoLists(left, right);
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
return mergeKLists(lists, 0, lists.size());
}
};
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
mergeKLists(0, 3)
├── mergeKLists(0, 1) → 返回 lists[0] (1 -> 4 -> 5)
└── mergeKLists(1, 3)
├── mergeKLists(1, 2) → 返回 lists[1] (1 -> 3 -> 4)
├── mergeKLists(2, 3) → 返回 lists[2] (2 -> 6)
└── mergeTwoLists(lists[1], lists[2]) → (1 -> 2 -> 3 -> 4 -> 6)
└── mergeTwoLists(lists[0], merge(lists[1], lists[2])) → (1 -> 1-> 2 -> 3 -> 4 -> 4-> 5 -> 6)
方法二:最小堆 / 优先级队列 priority_queue
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](const ListNode* a, const ListNode* b) {
return a->val > b->val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;
for (auto head : lists) {
if (head) {
pq.push(head);
}
}
ListNode* dummyhead = new ListNode(0);
ListNode* cur = dummyhead;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
if (node->next) {
pq.push(node->next);
}
cur->next = node;
cur = cur->next;
}
ListNode* newhead = dummyhead->next;
delete dummyhead;
return newhead;
}
};
这里使用 Lambda 表达式,Lambda 表达式把函数看作对象。Lambda 表达式可以像对象一样使用,比如可以将它们赋给变量和作为参数传递,还可以像函数一样对其求值。Lambda 表达式本质上与函数声明非常类似。Lambda 表达式具体形式如下:
[capture](parameters)->return-type{
body
};
[捕获列表](参数列表) -> 返回类型 {
// 函数体
};
其中:
-
[捕获列表]
:捕获外部变量的方式([]
表示不捕获任何变量,[=]
表示按值捕获,[&]
表示按引用捕获)。 -
(参数列表)
:定义传递给 Lambda 的参数(类似普通函数的参数)。 -
-> 返回类型
(可选):指定返回值类型(可以省略,由编译器推导)。 -
{ 函数体 }
:函数的具体实现。
这道题目中:
(1)定义 Lambda
[](ListNode* a, ListNode* b) { return a->val > b->val; }
(2)decltype(cmp) 用于自动推导 cmp 的类型,因为lambda没有名字。这样 priority_queue 就能正确使用 cmp进行排序。
(3)初始化 priority_queue,
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
-
ListNode*
是存储的数据类型。 -
vector<ListNode*>
是底层实现(默认vector
)。 -
decltype(cmp)
指定比较器的类型,pq(cmp)
传入cmp
作为构造函数参数。
当然也可以使用operator() 仿函数,对 () 进行重载
struct compare {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
priority_queue<ListNode*, vector<ListNode*>, compare> pq;
class Solution {
public:
struct cmp {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
for (auto head : lists) {
if (head) {
pq.push(head);
}
}
ListNode* dummyhead = new ListNode(0);
ListNode* cur = dummyhead;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
if (node->next) {
pq.push(node->next);
}
cur->next = node;
cur = cur->next;
}
ListNode* newhead = dummyhead->next;
delete dummyhead;
return newhead;
}
};
operator()
vs 普通函数
你可能会问:为什么不用普通函数,而要用 operator()
?
(1)普通函数:
bool myCompare(ListNode* a, ListNode* b) {
return a->val > b->val;
}
priority_queue<ListNode*, vector<ListNode*>, decltype(&myCompare)> pq(myCompare);
也可以,但 myCompare
需要用 &myCompare
传递,略显繁琐。使用 &myCompare
,表示传递的是函数指针。
(2)使用 operator()
(仿函数):
struct compare {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
priority_queue<ListNode*, vector<ListNode*>, compare> pq;
更简洁,priority_queue
直接使用 compare
作为类型。
(3)使用 lambda
(C++11):
auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
最简洁,省去 struct compare
定义,适用于单次使用。