23. Merge k Sorted Lists

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists) == 0:
            return None
        n = len(lists)
        interval = 1
        while interval < n:
            for i in range(0, n - interval, interval * 2):
                lists[i] = self.mergeTwoLists(lists[i], lists[i + interval])
            interval *= 2
        return lists[0]
    def mergeTwoLists(self, l1, l2):
        k = headNode = ListNode()
        while l1 and l2:
            if l1.val < l2.val:
                k.next = l1
                l1 = l1.next
            else:
                k.next = l2
                l2 = l2.next
            k = k.next
        k.next = l1 or l2
        return headNode.next