class Solution:
    #k: number of list
    #n: length of single list
    #TC: O(n log k) 
    #SC: O(log k) (because we call recursive)

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        n = len(lists)

        if n == 0:
            return None

        if n == 1:
            return lists[0]

        mid = n // 2

        l = self.mergeKLists(lists[:mid])
        r = self.mergeKLists(lists[mid:])

        return self.merge(l, r)

    def merge(self, l, r):

        dummy = ListNode(-1)
        head = dummy

        while(l and r):
            if l.val < r.val:
                head.next = l
                l = l.next
            else:
                head.next = r
                r = r.next

            head = head.next

        if l:
            head.next = l
        else:
            head.next = r

        return dummy.next