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


TAGS:
Divide and Conquer Linked List Heap
ANSWER:
Using Heap to control the current candidate of each linked lisk. Every time pop the next node to the result list, time
complexity is O(logk), the the overal time complexity is O(nklogk)

Other approach is merge each pair of the linked list, that make lists would be iterated multiple times, the final
time complexity would be O(nklogn)
"""

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

import heapq
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        h = [(lists[i].val, lists[i]) for i in xrange(len(lists)) if lists[i]]
        heapq.heapify(h)
        head = ListNode(0)
        cur = head
        while h:
            first = heapq.heappop(h)
            cur.next = ListNode(first[0])
            cur = cur.next
            if first[1].next:
                heapq.heappush(h,(first[1].next.val, first[1].next))
        return head.next

if __name__ == '__main__':
    print