LintCode Q104 Merge k Sorted Lists heapq in Python

  • Jinhai ZHOU
  • 4 Minutes
  • 2016年11月5日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
from heapq import heappush, heappop
class Solution:
"""
@param lists: a list of ListNode
@return: The head of one sorted list.
"""
def mergeKLists(self, lists):
# write your code here
if len(lists) == 0:
return None
elif len(lists) == 1:
return lists[0]
else:
min_heap = []
for list_node in lists:
while list_node is not None:
heappush(min_heap, list_node.val)
list_node = list_node.next
head = ListNode(None)
list_node = head
while min_heap:
list_node.next = ListNode(heappop(min_heap))
list_node = list_node.next
return head.next
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。