<gh_stars>0
"""
Leetcode(https://leetcode.com/problems/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) -> ListNode:
        if len(lists) == 0:
            return None
        if len(lists) == 1:
            return lists[0]
        mid = len(lists) // 2
        head2 = self.mergeKLists(lists[mid:])
        head1 = self.mergeKLists(lists[:mid])
        return self.merge2Lists(head1, head2)

    def merge2Lists(self, head1, head2):
        head = ListNode()
        cur = head
        while head1 and head2:
            if head1.val <= head2.val:
                cur.next = ListNode(head1.val)
                head1 = head1.next
            else:
                cur.next = ListNode(head2.val)
                head2 = head2.next
            cur = cur.next
        while head1:
            cur.next = ListNode(head1.val)
            head1 = head1.next
            cur = cur.next
        while head2:
            cur.next = ListNode(head2.val)
            head2 = head2.next
            cur = cur.next
        return head.next


# Leetcode solution - merge inplace w/ divide and conquer
# O(nlogk) Time | O(1) Space
# class Solution:
#     def mergeKLists(self, lists):
#         """
#         :type lists: List[ListNode]
#         :rtype: ListNode
#         """
#         amount = len(lists)
#         interval = 1
#         while interval < amount:
#             for i in range(0, amount - interval, interval * 2):
#                 lists[i] = self.merge2Lists(lists[i], lists[i + interval])
#             interval *= 2
#         return lists[0] if amount > 0 else None
#
#     def merge2Lists(self, l1, l2):
#         head = point = ListNode(0)
#         while l1 and l2:
#             if l1.val <= l2.val:
#                 point.next = l1
#                 l1 = l1.next
#             else:
#                 point.next = l2
#                 l2 = l1
#                 l1 = point.next.next
#             point = point.next
#         if not l1:
#             point.next = l2
#         else:
#             point.next = l1
#         return head.next


# class Solution:
#     def mergeKLists(self, lists) -> ListNode:
#         n = len(lists)
#         if n == 0:
#             return None
#         if n == 1:
#             return lists[0]
#         left = self.mergeKLists(lists[:n // 2])
#         right = self.mergeKLists(lists[n // 2:])
#         lst = self.merge(self.toList(left), self.toList(right))
#         return self.toNode(lst)
#
#     def merge(self, lst1, lst2):
#         if len(lst1) == 0:
#             return lst2
#         if len(lst2) == 0:
#             return lst1
#         ans = [0] * (len(lst1) + len(lst2))
#         l1, l2 = 0, 0
#         for i in range(len(ans)):
#             if l2 == len(lst2) or l1 < len(lst1) and lst1[l1] <= lst2[l2]:
#                 ans[i] = lst1[l1]
#                 l1 += 1
#             else:
#                 ans[i] = lst2[l2]
#                 l2 += 1
#         return ans
#
#     def toList(self, node):
#         ans = []
#         while node:
#             ans.append(node.val)
#             node = node.next
#         return ans
#
#     def toNode(self, lst):
#         if len(lst) == 0:
#             return None
#         node = ListNode(val=lst[0])
#         cur = node
#         for i in range(1, len(lst)):
#             cur.next = ListNode(val=lst[i])
#             cur = cur.next
#         return node
