"""
Merge k sorted linked lists and return it as one sorted list.
"""

from implementations import heap
from implementations import linked_list
from implementations.linked_list import LinkedList


def sort_k_linked_lists(*linked_lists):
    min_heap = heap.Heap(comp=lambda x, y: x.value < y.value)
    for lst in linked_lists:
        min_heap.insert(lst.head)

    result = LinkedList()
    while len(min_heap.items) > 0:
        item = min_heap.extract_min()
        if item.next:
            min_heap.insert(item.next)
        result.add(item.value)

    return result


if __name__ == '__main__':
    l1 = linked_list.create_linked_list([-3, 0, 1, 2, 6, 7])
    l2 = linked_list.create_linked_list([2, 4, 5, 10])
    l3 = linked_list.create_linked_list([1, 7, 9])
    print sort_k_linked_lists(l1, l2, l3)
