专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近一段时间关于京东进军外卖行业搞的沸沸扬扬，大家应该也都知道了，2月19日上午京东宣布，自2025年3月1日起，将逐步为京东外卖全职骑手缴纳“五险一金”，为兼职骑手提供意外险和健康医疗险。
结果当天下午美团平台发布消息，将为全国范围内的全职及稳定兼职骑手缴纳社保，预计2025年二季度开始实施，目前正在搭建骑手社保相关的信息系统。
不得不说京东这事干的漂亮，之前很多人在网上抱怨美团外卖很多都是外包的，不给交五险一金，美团也不当回事，无论怎么抱怨就是不交，这回竞争对手来了，就开始交了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第23题：合并 K 个升序链表。
问题描述
来源：LeetCode第23题
难度：困难
给你一个链表数组， 每个链表都已经按升序排列 。请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例1：
输入：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 == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4
问题分析
这题说的是给定一个已经排序好的链表，把它们合并成一个新的有序链表，如果是合并两个有序链表，只需要使用双指针即可。但这里是 k 个链表，总不能使用 k 个指针，当然使用 k 个指针也是可以的，这里我们使用另外一种方式，最小堆。
先把所有的链表添加到最小堆中，它会 按照链表的头节点排序 ，每次取出的都是头节点最小的链表。把取出的链表头节点移除之后，如果不为空，就继续添加到堆中，直到堆为空为止。
JAVA：
public ListNode mergeKLists(ListNode[] lists) { // 创建最小堆 PriorityQueue
pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.val)); ListNode dummy = new ListNode(); // 创建一个哑结点 ListNode tail = dummy; // 合并链表的尾节点 // 如果链表不为空，就把它添加到最小堆中 for (ListNode node : lists) if (node != null) pq.add(node); while (!pq.isEmpty()) { // 循环堆中的元素 tail.next = pq.poll(); // 获取堆中最小的节点 tail = tail.next; if (tail.next != null) // 如果链表不为空，重新添加到堆中。 pq.add(tail.next); } return dummy.next; }C++：
public: ListNode *mergeKLists(vector &lists) { // 自定义比较函数对象 struct cmp { bool operator()(const ListNode *a, const ListNode *b) { return a->val > b->val; } }; // 创建最小堆 priority_queue
vector , cmp> pq; auto *dummy = new ListNode(); // 创建一个哑结点 ListNode *tail = dummy; // 合并链表的尾节点 // 如果链表不为空，就把它添加到最小堆中 for (ListNode *node: lists) if (node) pq.push(node); while (!pq.empty()) { // 循环堆中的元素 tail->next = pq.top(); // 获取堆中最小的节点 pq.pop(); tail = tail->next; if (tail->next) // 如果链表不为空，重新添加到堆中。 pq.push(tail->next); } return dummy->next; }Python：
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: setattr(ListNode, "__lt__", lambda a, b: a.val < b.val) # 创建最小堆 pq = [] dummy = ListNode() # 创建一个哑结点 tail = dummy # 合并链表的尾节点 # 如果链表不为空，就把它添加到最小堆中 for node in lists: if node: heapq.heappush(pq, node) while pq: # 循环堆中的元素 tail.next = heapq.heappop(pq) # 获取堆中最小的节点 tail = tail.next if tail.next: # 如果链表不为空，重新添加到堆中。 heapq.heappush(pq, tail.next) return dummy.next笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴