專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

最近一段時間關(guān)于京東進(jìn)軍外賣行業(yè)搞的沸沸揚(yáng)揚(yáng)，大家應(yīng)該也都知道了，2月19日上午京東宣布，自2025年3月1日起，將逐步為京東外賣全職騎手繳納“五險一金”，為兼職騎手提供意外險和健康醫(yī)療險。

結(jié)果當(dāng)天下午美團(tuán)平臺發(fā)布消息，將為全國范圍內(nèi)的全職及穩(wěn)定兼職騎手繳納社保，預(yù)計(jì)2025年二季度開始實(shí)施，目前正在搭建騎手社保相關(guān)的信息系統(tǒng)。

不得不說京東這事干的漂亮，之前很多人在網(wǎng)上抱怨美團(tuán)外賣很多都是外包的，不給交五險一金，美團(tuán)也不當(dāng)回事，無論怎么抱怨就是不交，這回競爭對手來了，就開始交了。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第23題：合并 K 個升序鏈表。

問題描述

來源：LeetCode第23題

難度：困難

給你一個鏈表數(shù)組， 每個鏈表都已經(jīng)按升序排列 。請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

示例1：

輸入：lists = [[1,4,5],[1,3,4],[2,6]] 輸出：[1,1,2,3,4,4,5,6] 解釋：鏈表數(shù)組如下： [ 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

問題分析

這題說的是給定一個已經(jīng)排序好的鏈表，把它們合并成一個新的有序鏈表，如果是合并兩個有序鏈表，只需要使用雙指針即可。但這里是 k 個鏈表，總不能使用 k 個指針，當(dāng)然使用 k 個指針也是可以的，這里我們使用另外一種方式，最小堆。

先把所有的鏈表添加到最小堆中，它會 按照鏈表的頭節(jié)點(diǎn)排序 ，每次取出的都是頭節(jié)點(diǎn)最小的鏈表。把取出的鏈表頭節(jié)點(diǎn)移除之后，如果不為空，就繼續(xù)添加到堆中，直到堆為空為止。

JAVA：

public ListNode mergeKLists(ListNode[] lists) {     // 創(chuàng)建最小堆     PriorityQueue
         
         
  pq =  new PriorityQueue<>(Comparator.comparingInt(a -> a.val));     ListNode dummy =  new ListNode(); // 創(chuàng)建一個啞結(jié)點(diǎn)     ListNode tail = dummy; // 合并鏈表的尾節(jié)點(diǎn)      // 如果鏈表不為空，就把它添加到最小堆中      for (ListNode node : lists)          if (node !=  null)             pq.add(node);      while (!pq.isEmpty()) { // 循環(huán)堆中的元素         tail.next = pq.poll(); // 獲取堆中最小的節(jié)點(diǎn)         tail = tail.next;          if (tail.next !=  null) // 如果鏈表不為空，重新添加到堆中。             pq.add(tail.next);     }      return dummy.next; }

C++：

public:     ListNode *mergeKLists(vector  &lists)  {         // 自定義比較函數(shù)對象         struct cmp {             bool operator()(const ListNode *a, const ListNode *b) {                 return a->val > b->val;             }         };         // 創(chuàng)建最小堆         priority_queue
         
         
 vector , cmp> pq;          auto *dummy =  new ListNode(); // 創(chuàng)建一個啞結(jié)點(diǎn)         ListNode *tail = dummy; // 合并鏈表的尾節(jié)點(diǎn)          // 如果鏈表不為空，就把它添加到最小堆中          for (ListNode *node: lists)              if (node)                 pq.push(node);          while (!pq.empty()) { // 循環(huán)堆中的元素             tail->next = pq.top(); // 獲取堆中最小的節(jié)點(diǎn)             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)     # 創(chuàng)建最小堆     pq = []     dummy = ListNode()  # 創(chuàng)建一個啞結(jié)點(diǎn)     tail = dummy  # 合并鏈表的尾節(jié)點(diǎn)     # 如果鏈表不為空，就把它添加到最小堆中     for node in lists:         if node:             heapq.heappush(pq, node)     while pq:  # 循環(huán)堆中的元素         tail.next = heapq.heappop(pq)  # 獲取堆中最小的節(jié)點(diǎn)         tail = tail.next         if tail.next:  # 如果鏈表不為空，重新添加到堆中。             heapq.heappush(pq, tail.next)     return dummy.next

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計(jì)做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。