專欄：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算法文檔 。