lintcode 104. 合并k个排序链表优先队列

傷城~ 2023-07-03 07:08 2阅读 0赞

合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。

样例
    样例 1:
    	输入:   [2->4->null,null,-1->null]
    	输出:  -1->2->4->null
    
    样例 2:
    	输入: [2->6->null,5->null,7->null]
    	输出:  2->5->6->7->null

/**
     * Definition of ListNode
     * class ListNode {
     * public:
     *     int val;
     *     ListNode *next;
     *     ListNode(int val) {
     *         this->val = val;
     *         this->next = NULL;
     *     }
     * }
     */
    class Solution {
        
    public:
        /**
         * @param lists: a list of ListNode
         * @return: The head of one sorted list.
         */
        struct cmp
        {
        
            bool operator()(ListNode*a,ListNode*b)
            {
        
                return a->val>b->val;
            }
        };
        ListNode *mergeKLists(vector<ListNode *> &lists) {
        
            // write your code here
            priority_queue<ListNode*, vector<ListNode *>,cmp> minHeap;
            for(int i=0; i< lists.size();i++)
            {
        
                if(lists[i]!=NULL) minHeap.push(lists[i]);
            }
            ListNode *tmp=NULL,*newhead=NULL,*current=NULL;
            while(!minHeap.empty())
            {
        
                tmp=minHeap.top();
                minHeap.pop();
                if(current==NULL) newhead=tmp;
                else current->next=tmp;
                current=tmp;
                if(tmp->next!=NULL) minHeap.push(tmp->next);
            }
            return newhead;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关 lintcode486. 合并k个排序数组

将 k 个有序数组合并为一个大的有序数组。样例样例 1: 输入: [ [1, 3, 5, 7],

电玩女神/ 2023年07月06日 06:12/ 0 赞/ 2 阅读

相关 lintcode 104. 合并k个排序链表优先队列

合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。样例样例 1: 输入: [2->4->null,null,-1->nul

傷城~/ 2023年07月03日 07:08/ 0 赞/ 3 阅读

相关 23. 合并K个升序链表(优先队列)

\\\ 解题思路首先将每个链表的头节点加入优先队列,然后依次将优先队列的头节点拼接到新的链表头上去,并将该头节点的下一个节点加入优先队列(要注意判断空节点) \\\ 代码

骑猪看日落/ 2022年10月28日 15:19/ 0 赞/ 196 阅读

相关 LeetCode23. 合并K个升序链表【优先队列】

难度：困难题目描述： > 给你一个链表数组，每个链表都已经按升序排列。 > > 请你将所有链表合并到一个升序链表中，返回合并后的链表。示例 1：输入： >

﹏ヽ暗。殇╰゛Y/ 2022年09月09日 06:03/ 0 赞/ 230 阅读

相关【LintCode 简单】165. 合并两个排序链表

1.问题描述：将两个排序链表合并为一个新的排序链表。 2.样例: 给出 `1->3->8->11->15->null`，`2->null`，返回 `1->2->

小灰灰/ 2022年06月01日 04:08/ 0 赞/ 186 阅读

相关合并 k 个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: 输入: [ 1->4->5, 1->3->4,

傷城~/ 2022年04月22日 11:46/ 0 赞/ 155 阅读

相关合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: 输入: [ 1->4->5, 1->3->4,

男娘i/ 2022年01月20日 04:07/ 0 赞/ 191 阅读

相关合并K个排序链表

题目描述合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: 输入: [ 1->4->5, 1->

雨点打透心脏的1/2处/ 2022年01月14日 23:35/ 0 赞/ 206 阅读

相关 23. 合并K个排序链表

> 知乎ID: 码蹄疾 > 码蹄疾，毕业于哈尔滨工业大学。 > 小米广告第三代广告引擎的设计者、开发者； > 负责小米应用商店、日历、开屏广告业务线研发；

痛定思痛。/ 2021年12月17日 08:53/ 0 赞/ 242 阅读

相关合并K个排序链表

合并K个排序链表题目描述 ![5057999-3fd09622a0f9a1f2.png][] 基本思路这道题属于双链表合并的进阶。理解这道题首先需要了解

清疚/ 2021年10月01日 11:26/ 0 赞/ 279 阅读