写在前面大家好我最近刚刚开始接触 C也是刚刚开始接触算法。这几天在学习 C 链表时我的心情可以说是像过山车一样。以前习惯了 C 语言里苦哈哈地用malloc分配内存、小心翼翼地处理NULL指针的我在接触到 C 的构造函数和虚拟头节点后虽然说刚开始接受起来还是有点困难但好在最终还是克服了。趁着热乎劲我在 LeetCode 上用 C 轻松搞定了第 21 题合并两个有序链表。我自信满满地点击了下一题实不相瞒这道合并 K 个升序序列题目的 Hard 标签确实吓到我了我还不觉得自己有独立解决困难题目的能力。但经过一番挣扎我发现只要转变思维借用 C 的优势初学者也完全可以对 Hard 题进行降维打击今天我就从一个初学者的视角一步步撕开这道题的外衣并尽可能详细地把优先队列这一知识点解释通透。1. 题目初探题目描述很简单给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。下面是 Leetcode 官方的示例输入lists [[1,4,5],[1,3,4],[2,6]] 输出[1,1,2,3,4,4,5,6] 解释链表数组如下 [ 1-4-5, 1-3-4, 2-6 ] 将它们合并到一个有序链表中得到。 1-1-2-3-4-4-5-6对于这道题大家可以带入一下生活桌子上有 K 叠已经从小到大理好的扑克牌。现在你的任务是把它们合并成一叠全新且有序的扑克牌你会怎么做2. 破局思路一开始我完全没有思路但我突然想到我刚刚不是才写过合并 2 个链表的代码吗这两道题颇有相似之处。只能合并两叠牌的代码我已经写过了那合并 K 叠牌的暴力解法不就有了吗我先把第 1 叠和第 2 叠放进机器融合成一大叠。我拿着这新的一大叠再和第 3 叠放进机器……一直循环 K-1 次成功。我直接复用第 21 题的代码把它封装成一个mergeTwoLists函数然后用一个for循环搞定。提交代码之后也是成功通过了但就是耗时长的吓人有 100 多毫秒。但冷静下来一算时间复杂度越到后面合并后的链表就越长每次都要从头遍历全部的节点如果在真实的项目中早就卡死了。在看了评论区的大神的解法之后我才意识到C 远没有我想象的这么简单真正的大杀器才刚刚登场。3. 优先队列的降维打击有没有一种方法不需要我们辛辛苦苦地两条链表互相比较有的C 的 STL 标准模板库中有一个和这道题简直是天生一对的工具——优先队列。3.1 什么是优先队列从它的名字我们就能看出来它不是普通的队列当然这好像是一句废话。普通队列就是将就一个先来后到。而优先队列就像是医院的急诊室谁的病重谁先进去。不管你扔进去多少个数据只要你调用出队指令它总是自动把最极端的那个数据最大或最小弹出来。3.2 新的解题思路有了这个工具我们的合并逻辑变得极其方便把 K 叠牌的最上面那一张也就是 K 个链表的头节点全部放进优先队列里面。让优先队列弹出最上面的那一个头节点根据题目我们要让最上面的头节点的val最小。然后看看刚刚拿走的那张牌属于哪一叠从那一叠里再摸下一张牌放进优先队列里补充。一直重复拿牌和补充直到优先队列空了所有链表就完美合并了。因为盒子里最多只有 K 个节点利用优先队列内部的二叉树结构每次放进去或拿出来的时间复杂度只有O(logK)。总时间复杂度瞬间降维到O(NlogK)运行速度相当的快。4. 优先队列详解思路现在已经很完美了但是这里还有些坑。在 C 中引入#include queue后如果只存整数写priority_queueint pq就行了。但现在我们要存的是链表节点指针ListNode*如果依旧按照常规的方法来写他就会去比较内存地址的大小这不是乱套了吗这就引出了 C 优先队列的完整体模板结构包含三个参数priority_queue 数据类型, 底层容器类型, 比较规则 在 C 中我们通常用仿函数来定义比较规则。这看起来有点吓人但其实就是个重写了()的结构体//比较规则structcmp{booloperator()(ListNode*a,ListNode*b){//优先队列默认是大顶堆。//我们要从小到大排也就是小顶堆所以要反着来用大于号//如果 a 的值大于 b就把 a 沉到下面去。returna-valb-val;}};当优先队列需要比较两个元素时调用cmp()(a, b)。如果返回truea 的优先级低于ba 会被放在堆的下面。如果返回falsea 的优先级高于ba 会被放在堆的上面。我们来梳理一下它的工作原理最后返回的是a-val b-val也就是说当a的val比b的val小时返回false这时a的优先级高于ba会被放在堆的上面正是我们要的结果。定义好规则后我们的优先队列就彻底成型了priority_queueListNode*,vectorListNode*,cmppq;5. 完整代码classSolution{public:structcmp{booloperator()(ListNode*a,ListNode*b){returna-valb-val;//小顶端}};ListNode*mergeKLists(vectorListNode*lists){priority_queueListNode*,vectorListNode*,cmppq;ListNode*dummynewListNode(0);ListNode*currdummy;for(inti0;ilists.size();i){if(lists[i]!nullptr)//必须判断是否为空如果为空还放到优先队列会导致后面minNode-next非法解引用{pq.push(lists[i]);//将所有链表头节点塞入优先队列}}while(!pq.empty())//优先队列不空{ListNode*minNodepq.top();//把最小的拿出来用于后面找它所在的那一叠的下一个节点pq.pop();//弹出最小的curr-nextminNode;//将最小的节点接到我们的新链表上currcurr-next;//让curr指针向后移动一位if(minNode-next!nullptr)//找到刚才弹出的最小节点所在的链表只要下一个节点不为空就塞到优先队列{pq.push(minNode-next);}}ListNode*resultdummy-next;deletedummy;returnresult;}};写在最后回首这几天从 C 语言向 C 跃迁的历程我有了些深刻的感悟关乎我们面对生活和挑战的真实态度。如果你也是一个刚刚踏上编程之路或者正在被某个 Hard 标签的题目按在地上摩擦的初学者我想对你说不要慌张也不要畏惧。底层的功夫慢慢的扎高级的工具勇敢去学。只要逻辑的指针不断向前curr ! nullptr即使再长的链表我们也终将抵达理想的彼岸。本文结束。