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