# Merge K Sorted Lists (LC version 3.03).

from heapq import heappush, heappop

# List.

class ListNode:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next

def makeList(seq):
    n = None
    for x in reversed(seq):
        n = ListNode(x, n)
    return n

def printList(n):
    a = []
    while n:
        a.append(n.val)
        n = n.next
    print('List(', a, ')', sep='')

# Merge.

def mergeKLists(lists):
    # Push list heads to heap keyed on node.val and a secondary integer.
    # The secondary keys serve a dual purpose:
    #
    #  1. The unique keys prevent the comparison from reaching the node
    #     element which is not comparable.
    #  2. The keys are ordered ascending with respect to the list input
    #     ensuring stability for equal valued elements.

    heap = []
    for k, n in enumerate(lists):
        if n:
            heappush(heap, (n.val, k, n))

    # The heap maintains the smallest valued head node for all lists at
    # its front. The node is appended to the result and heap is updated
    # with its next node as the new list head. The loop exits when only
    # a single list remains.

    temp = ListNode()
    if heap:
        t = temp
        while True:
            _, k, n = heappop(heap)
            t.next = n
            if not heap:
                break
            t = t.next
            n = n.next
            if n:
                heappush(heap, (n.val, k, n))
    return temp.next

# Show.

l0 = makeList([])
l1 = makeList([1, 3, 5, 7])
l2 = makeList([2, 4, 6])
l3 = makeList([0, 4, 8])

printList(l0)
printList(l1)
printList(l2)
printList(l3)

printList(mergeKLists([]))
printList(mergeKLists([l0]))
printList(mergeKLists([l1]))
printList(mergeKLists([l1, l2, l3]))