Description
Merge k sorted linked lists and return it as one sorted list.
Solution
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
ListNode.__lt__ = lambda x,y : x.val < y.val
import heapq
class Solution:
"""
@param lists: a list of ListNode
@return: The head of one sorted list.
"""
def mergeKLists(self, lists):
# write your code here
head = tail = None
self.heap =[]
heapq.heapify(self.heap)
for l in lists:
if l is None:
continue
heapq.heappush(self.heap,l)
while len(self.heap):
min_p = heapq.heappop(self.heap)
if head is None:
head = min_p
tail = head
else:
tail.next = min_p
tail = min_p
if min_p.next is not None:
heapq.heappush(self.heap,min_p.next)
return head
