【leetcode100-034】【链表/优先队列】合并k个升序链表

发布时间:2024-01-09 00:04:48

【题干】

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

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

【思路】

  • 其实就是多路归并
  • 用一个优先队列简化k个头部的比较和选最小节点的过程
  • 然后就只剩一些细节处理啦
  • 都没啥好写的今天这题。。。

【题解】

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

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