新学的C++17的推导指引
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
lists.erase(remove_if(lists.begin(), lists.end(), [](auto p) { return !p; }), lists.end());
priority_queue q{ [](auto& a, auto& b) { return a->val > b->val; }, lists };
ListNode head;
for (auto p = &head; !q.empty(); q.pop()) {
p = p->next = q.top();
if (p->next) q.push(p->next);
}
return head.next;
}
};
让我们逐步解释代码:
lists.erase(remove_if(lists.begin(), lists.end(), [](auto p) { return !p; }), lists.end());
这行代码使用了STL(标准模板库)中的 remove_if 函数和 erase 函数,结合 lambda 表达式进行列表的操作。
remove_if(lists.begin(), lists.end(), [](auto p) { return !p; }):
remove_if 函数接受一个范围(在这里是 lists.begin() 到 lists.end())和一个谓词(在这里是 lambda
表达式)。
谓词 [](auto p) { return !p; } 是一个匿名函数,它返回一个布尔值,用于判断是否移除某个元素。在这里,!p
判断指针 p 是否为空,如果为空则返回 true,表示需要移除。 remove_if
函数将满足条件的元素移动到容器的末尾,并返回一个指向新的逻辑结尾的迭代器。 erase(lists.end()):
erase 函数接受一个迭代器参数,表示要从容器中删除的位置。在这里,我们传入了 remove_if 的返回值,即移除元素后的新逻辑结尾。
erase 函数会删除从指定位置到容器末尾的所有元素。
综合起来,这行代码的作用是移除 lists 中值为 nullptr 的元素。首先使用 remove_if 将满足条件的元素移到末尾,然后通过 erase 删除这些元素,最终 lists 中不包含值为 nullptr 的元素。这通常用于清理掉链表中的空指针。
priority_queue q{ [](auto& a, auto& b) { return a->val > b->val; }, lists };
创建一个优先队列 q,其中的元素类型是 ListNode* 指针。使用 lambda 表达式定义比较函数,使得队列按照链表节点的值从小到大排列。初始值为 lists 中的链表指针。
ListNode head;
创建一个新的链表头节点。
for (auto p = &head; !q.empty(); q.pop()) { ... }
迭代优先队列,每次取出队列中值最小的节点,并将其连接到新链表的尾部。
p = p->next = q.top();
将当前节点指针 p 指向队列中值最小的节点,并将其接入新链表。
代码会先执行右边的等号,即 p->next = q.top();,然后再执行左边的等号,即 p = p->next;。
这是因为 C++ 中赋值运算符的结合性是从右向左的。所以首先将 q.top() 的值赋给 p->next,然后将 p->next 的值再赋给 p。这样做的效果是,p 和 p->next 都指向了 q.top() 所指向的节点,即将 q.top() 接入了新链表。
这种连续赋值的写法是 C++ 中的一种常见用法,可以简洁地实现链式赋值。
if (p->next) q.push(p->next);
如果当前节点的下一个节点不为空,将其加入优先队列,继续保持队列有序。
return head.next;
返回合并后链表的头节点。
这个算法的关键在于使用优先队列来维护 K 个链表中当前值最小的节点,通过不断取出最小节点并将其后一个节点插入队列,实现链表的合并。