LeetCode:23 Merge k Sorted Lists

problem

LeetCode 23. Merge k Sorted Lists

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

solution

方法一

思路过程

用堆排序，思路可以查考使用堆(heap)(官解中的"归并排序")思路详解；另附Python heapq模块用法解释这篇文章，将算法的思路解析得很清晰，然后运用过来就行了

代码

python

import heapq class Solution: def mergeKLists(self, lists): length = len(lists) # 有没有可能第一个就是None end = 0 heap = [] # 用来当作头节点 res = ListNode(0) temp = res for i in range(length): if lists[i]: # heap.append((lists[i].val, lists[i])) # 所有都遍历完毕的时候就跳出循环 # 这里heapq。heapify(heap)似乎有相同值时，会对列表中下一个元素排序，但是后面是ListNode，报错 # TypeError: '<' not supported between instances of 'ListNode' and 'ListNode' # heapq.heapify(heap) # 所以改成下面这样的，每层不一样就区分了不同的元素 heap.append((lists[i].val, i, lists[i])) else: end += 1 heapq.heapify(heap) while end != length: value, i, node = heapq.heappop(heap) temp.next = node temp = node if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) else: end += 1 return res.next

方法二

思路过程

两两合并，最核心的部分可以先练习LeetCode 21. Merge Two Sorted Lists，那么这个题就迎刃而解了

代码

python

#迭代 class Solution: def merge2lists(self, list1, list2): res = ListNode(0) temp = res while list1 and list2: if list1.val < list2.val: temp.next = list1 list1 = list1.next else: temp.next = list2 list2 = list2.next temp = temp.next temp.next = list1 if list1 else list2 return res.next def iterativemerge(self, left, right, lists): if left == right: return lists[left] mid = left + (right - left) // 2 leftlist = self.iterativemerge(left, mid, lists) rightlist = self.iterativemerge(mid + 1, right, lists) return self.merge2lists(leftlist, rightlist) def mergeKLists(self, lists) -> ListNode: length = len(lists) if length == 0: return None return self.iterativemerge(0, length - 1, lists)

python

#递归 class Solution: def merge2lists(self, list1, list2): if not list1: return list2 if not list2: return list1 if list1.val < list2.val: list1.next = self.merge2lists(list1.next, list2) return list1 else: list2.next = self.merge2lists(list1, list2.next) return list2 def recursionmerge(self, left, right, lists): if left == right: return lists[left] mid = left + (right - left) // 2 leftlist = self.recursionmerge(left, mid, lists) rightlist = self.recursionmerge(mid + 1, right, lists) return self.merge2lists(leftlist, rightlist) def mergeKLists(self, lists) -> ListNode: length = len(lists) if length == 0: return None return self.recursionmerge(0, length - 1, lists)