合併K個排序鏈表

• 2019 年 10 月 5 日
• 筆記

合併K個排序鏈表

0.說在前面1.合併K個排序鏈表2.作者的話

0.說在前面

每周兩篇leetcode刷題，今天本周第二篇，一起來看合併K個排序鏈表，下面一起來實戰吧！

1.合併K個排序鏈表

問題

合併 k 個排序鏈表，返回合併後的排序鏈表。請分析和描述演算法的複雜度。

示例:

輸入:  [    1->4->5,    1->3->4,    2->6  ]  輸出: 1->1->2->3->4->4->5->6  

演算法一

【思想】

遍歷k個鏈表，將每個鏈表中的節點值添加到list當中，然後排序，創建新鏈表！

【實現】

def mergeKLists(self, lists):          all_list=[]          for each in lists:              while each:                  all_list.append(each.val)                  each=each.next          all_list.sort()          head=ListNode(0)          p=head          for i in all_list:              p.next=ListNode(i)              p=p.next          p.next=None          p=head.next          del head          return p  

【分析】

假設其中最長鏈表長度為n，則時間複雜度為O(nk)，空間複雜度為O(n)。

演算法二

【思想】

兩兩鏈表合併，合併的時候採用遞歸進行合併，直到最後合併成一個鏈表，返回即可！

【實現】

class Solution:      def mergeKLists(self, lists):          """          :type lists: List[ListNode]          :rtype: ListNode          """          interval = 1          lists_len = len(lists)          while interval<lists_len:              for i in range(0,lists_len-interval,interval * 2):                  lists[i] = self.merge(lists[i], lists[i + interval]);              interval *= 2          return lists[0] if len(lists) > 0 else None      def merge(self,l1, l2):          if l1 is None:              return l2          if l2 is None:              return l1          if l1.val < l2.val:              l1.next = self.merge(l1.next, l2)              return l1          else:              l2.next = self.merge(l1, l2.next)              return l2  

【分析】

假設其中最長鏈表長度為n，兩兩合併時間複雜度O(n)，每個鏈表遍歷一次O(k)則，時間複雜度為O(nk)，空間複雜度為O(1)。