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


class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        # Divide and conquer using two way mergeL O(nk log(k)) runtime O(1) space
        if len(lists) == 0:
            return None
        end = len(lists) - 1
        while end > 0:
            begin = 0
            while begin < end:
                lists[begin] = self.mergeTwoLists(lists[begin], lists[end])
                begin += 1
                end -= 1
        return lists[0]

    def mergeTwoLists(self, l1, l2):
        dummyHead = ListNode(0)
        p = dummyHead
        while l1 and l2:
            if l1.val < l2.val:
                p.next = l1
                l1 = l1.next
            else:
                p.next = l2
                l2 = l2.next
            p = p.next
        if l1:
            p.next = l1
        if l2:
            p.next = l2
        return dummyHead.next


def arrToList(arr):
    temp = None
    for x in reversed(arr):
        head = ListNode(x)
        head.next = temp
        temp = head
    return head


def print_list(node):
    while node:
        print(node.val, end=" ")
        node = node.next
    print()


def test():
    arr1 = [1, 2, 4, 7, 19]
    arr2 = [-3, 6, 8, 9, 18]
    arr3 = [3]

    head1 = arrToList(arr1)
    head2 = arrToList(arr2)
    head3 = arrToList(arr3)

    headList = [head2, head3, head1]

    # newhead = Solution().mergeTwoLists(head1, head2)
    newhead = Solution().mergeKLists(headList)
    print_list(newhead)

test()
