LeetCode 23 Hard，K個鏈表歸併

2020 年 3 月 5 日
筆記

鏈接

https://leetcode.com/problems/merge-k-sorted-lists/

難度

Hard

描述

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

給定K個有序鏈表，要求將它所有的元素歸併到一個鏈表，並且有序。

樣例:

Input:  [     1->4->5,    1->3->4,    2->6  ]  Output: 1- >1->2->3->4->4->5->6

題解

按照慣例，我們還是先來看最簡單的解法，也就是暴力法。

暴力

這題當中，暴力的方法也很簡單，非常簡單粗暴，那就是先把所有元素取出來，排序之後再放到鏈表當中去。但是這麼做說實話有點脫褲子放屁，我們分析一下複雜度也會發現，假設所有的元素個數是n，那麼最後的複雜度應該就是排序所消耗的複雜度，也就是，和K沒有一點關係，而且我們也完全沒有用上這K個鏈表當中的元素都是有序的這個信息，顯然這是不科學的。

我們對上面的純暴力方法稍稍做一些優化，想辦法把K個鏈表當中元素有序的信息用上。用上的方法也很簡單，我們之前做歸併排序的時候曾經做過兩個數組的歸併，我們用同樣的方法，只不過我們這次換成是K個鏈表而已。也就是說我們每次遍歷這K個鏈表的頭元素，從其中取出最小的那個元素插入最後的結果鏈表當中，當所有鏈表為空的時候，說明所有的元素已經歸併完了，那麼進行返回。

我們來試着寫一下代碼：

class Solution:      def mergeKLists(self, lists: List[ListNode]) -> ListNode:          import sys            ret = ListNode(0)          pnt = ret            while True:              mini = sys.maxsize              node = None              # 遍歷所有的鏈表              for i, l in enumerate(lists):                  if l is None:                      continue                  if l.val < mini:                      mini = l.val                      node = i              # 如果node為None，說明所有的元素都已經歸併結束了              if node is None:                  break              pnt.next = ListNode(mini)              pnt = pnt.next              lists[node] = lists[node].next          return ret.next

這種算法的複雜度是多少呢？稍微算一下就知道，我們每一次選擇數的時候，都需要遍歷K個鏈表的頭指針。一共有n個元素，所以總體的複雜度是。和之前暴力的方法相比如何呢？其實是半斤八兩，這兩者誰大誰小完全取決於K和的大小關係。一般來說n不會超過一千萬，所以不會很大，粗略估算，不會超過30，而K很有可能超過30。也就是說大部分情況下這種方法的運算時間要比暴力還要長。

看起來這個用上了鏈表內元素大小關係濃眉大眼的歸併法，還不如之前簡單粗暴的暴力來得管用。實在是有點粉刺。

歸併

我們回想一下從前，在之前的問題當中，我們遇到比較多的往往是兩個數組的歸併，這次是K個鏈表，因此複雜度增加了許多。那麼我們能不能把這K個鏈表看成是兩兩鏈表的組合呢？我們每次將這些鏈表兩兩分組，然後歸併之後再次兩兩分組歸併，直到最後只剩下一個鏈表為止，這種方案會不會更優一些呢？

我們畫張圖來看看這一過程：

我們橫向來看，在每一次merging階段當中，我們都遍歷了全部的元素，所以每一層總體的複雜度是。那麼，我們一共又遍歷了多少層呢？也不難，我們每次merging，鏈表的數量都會減少一半。一共有K個鏈表，那麼顯然，應該要merging 次，也就是說有個merging階段，所以總體的複雜度是。由於K不會太大，所以這種方法顯然要優於和.

我們先來寫出兩個鏈表歸併的代碼，之後再遞歸的形式調用即可：

class Solution:        def mergeTwoList(self, l1, l2):          ret = ListNode(0)          pnt = ret          while True:              """              鏈表沒辦法像數組那樣在末尾插入標兵了              所以只能人工判斷是否為空的情況              """              if l1 is None and l2 is None:                  break              if l1 is None:                  pnt.next = ListNode(l2.val)                  pnt = pnt.next                  l2 = l2.next              elif l2 is None:                  pnt.next = ListNode(l1.val)                  pnt = pnt.next                  l1 = l1.next              else:                  if l1.val < l2.val:                      pnt.next = ListNode(l1.val)                      l1 = l1.next                  else:                      pnt.next = ListNode(l2.val)                      l2 = l2.next                  pnt = pnt.next          return ret.next        def dfs(self, lists, l, r):          """          遞歸合併K個鏈表          這裡的l和r維護的是閉區間          """          if l > r:              return None          if l == r:              return lists[l]          else:              mid = (l + r) // 2              return self.mergeTwoList(self.dfs(lists, l, mid), self.dfs(lists, mid+1, r))        def mergeKLists(self, lists: List[ListNode]) -> ListNode:          # 傳入l=0， r=len(lists)-1，因為是閉區間          return self.dfs(lists, 0, len(lists)-1)

優先隊列

到這裡還沒有結束，下面要介紹的是可以說是我個人覺得這題最棒的解法了，就是使用我們之前說的優先隊列。還記得嗎，優先隊列可以自動保證隊列當中的元素有序。只要利用優先隊列，然後將當前第一個元素作為優先級，讓優先隊列幫我們維護隊列當中的順序。通過使用優先隊列，我們的代碼無論是可讀性還是編碼複雜度都會大大降低。

如果有新關注的，或者是已經遺忘了優先隊列用法的同學可以點擊下方鏈接，回顧一下優先隊列的用法：Python應用——優先隊列與heapq

class Solution:        def mergeKLists(self, lists: List[ListNode]) -> ListNode:          class Node:              """              存儲在優先隊列當中的節點              """              def __init__(self, val, arr):                  self.val = val                  self.arr = arr                # 重載判斷大小的比較函數              def __lt__(self, other):                  return self.val < other.val            import heapq          arr = []          # 將所有鏈表插入優先隊列當中          for l in lists:              if l is not None:                  heapq.heappush(arr, Node(l.val, l.next))            ret = ListNode(0)          pnt = ret            while len(arr) > 0:              # 從優先隊列頭部獲取元素，需要注意，pop之後元素會從隊列中刪除              node = heapq.heappop(arr)              val, l = node.val, node.arr              pnt.next = ListNode(val)              pnt = pnt.next                # 獲取完頭部元素之後，將剩下的鏈表插入回隊列當中              if l is not None:                  heapq.heappush(arr, Node(l.val, l.next))            return ret.next

這種方法從代碼複雜度上要比上一種要小很多，但是我們來分析一下會發現，對於優先隊列而言，每次插入的複雜度是，由於我們一共有K個鏈表，所以插入的複雜度是，一共有n個元素，所以最終的複雜度依然是和歸併的方法是一樣的。但是數據結構的使用簡化了我們計算的過程，這也是我們之所以學習各種數據結構的原因和意義。

今天這道題呢雖然掛的難度是Hard，但其實並不難，哪怕是我們暴力求解都可以通過。因此希望大家不要被它上面寫的難度所嚇到，另外，這題對於優先隊列的應用也非常經典，非常值得學習。

今天的文章就是這些，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的舉手之勞對我來說很重要。