美团宣布将为外卖骑手缴纳社保。

专栏：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算法文档 。