# Merge K Sorted Lists (LC version 3.02).

from heapq import heappush, heappop

# List.

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

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

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

# Merge.

def mergeKLists(lists):
    #
    # Add lists to heap keyed on node.val; a second integer key is used
    # and serves 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. This node is appended to temp and replaced by its next
    # node in the heap 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]))