合并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)。