23. 合并 K 个升序链表

发布时间:2024年01月19日

新学的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 个链表中当前值最小的节点,通过不断取出最小节点并将其后一个节点插入队列,实现链表的合并。

文章来源:https://blog.csdn.net/m0_48711099/article/details/135688440
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。