2020.4.26合并K个排序链表

题目呈现如下:

题目传送门

思路介绍:

这题我的思路比较简单.简明表示如下:

• 1.取个链上第一个元素,建立最小堆.
• 2.将堆顶取出放入res尾部,若其后元素不为空,则取出放入最小堆,并对最小堆进行维护.
• 3.重复2,直至堆空.将链表输出.

实现细节:

虚拟头节点

作用:初始化链表,使得之后每次在链表尾部添加元素都变得完全一样,很大程度减少了代码量.

STL中的priority_queue及仿函数functor

包含在头文件queue中,可以方便地维护一个有一定优先级的队列,也就是堆.定义有三个参数:数据、容器(用数组实现的容器,包含vector、deqeue，不包含list)、比较方式(仿函数).
何为仿函数呢?简而言之,就是一个表现和函数很像的类(或是结构体).在此例中,封装了struct functional,里面只实现了operator()的override.
需要注意的是greater比较方式维护的是小顶堆(原因我盲猜:比较方式是用于决定是否"下沉",大的下沉那么对应的就是小顶堆).

下附AC代码

struct functional {
         bool operator() (ListNode* n1, ListNode* n2) {
             return n1->val > n2->val; // 小顶堆
        }
    };
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(!lists.size()) return NULL;
        ListNode* dummyHead = new ListNode(0); // 虚拟头节点
        ListNode* cur = dummyHead;
        priority_queue<ListNode*,vector<ListNode*>,functional> pq;
        vector<ListNode*>::iterator ite=lists.begin();
        for(auto p:lists){
        if(p!=NULL){
            pq.push(p);
        }
       }
        // while(ite!=lists.end()) { // 各个链表第一个节点压入优先队列
        //     if(*ite==NULL) continue;
        //     pq.push(*ite);
        // }
        while(!pq.empty()) {
            ListNode* nxt = pq.top();
            pq.pop();
            cur->next = nxt;
            cur = cur->next;
            if(nxt->next!=NULL) {
                pq.push(nxt->next);
            }
        }
        return dummyHead->next;
        
    }
};

番外:

由本篇,我开始正式了在cnblogs的写作,以往尝试了hexo+github、云服务器部署wordpress两种方式,但是由于各种原因,兜兜转转最终来到了博客园.
拥有自己博客的想法发端于刚接触编程,开始逛CSDN那会儿,感觉能够让自己的知识能够帮助别人,是一件很振奋的事情,这也算是一种感情上的变现吧.毕竟学习的过程,很多时候是没有太多正向反馈的??
不过其实,在博客园写博客,更多地应该是在孤芳自赏吧.酒香不怕巷子深这句俗语,在流量为王、行业头部甚嚣尘上的现今,已经黯淡失色.博客园正是用以一种几乎看不见盈利的运营模式给上万的用户提供一个自发运动的平台,这很酷.我觉得也酷.只要博客园不关停,我想,博客园会一直成为我兴风作浪的一个窝点.
说说我这个每日系列(显然由于咕咕,存在日变周,周变月的可能...),目标是提高自己基础的码农素养,小目标是刷200+的力扣题以及CCF-CSP的一些题目.
最后,如高考前夕我QQ签名那样--我祝自己,功不唐捐,也祝愿读者你能够笑口常开??

[0]力扣每日一题

原文：https://www.cnblogs.com/tsuipo/p/12783748.html