# Leetcode 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[Optional[ListNode]]) -> Optional[ListNode]:
        def merge(list1: ListNode, list2: ListNode):
            dummy = ListNode()
            p = dummy
            l1 = list1
            l2 = list2
            while l1 and l2:
                if l1.val < l2.val:
                    p.next = l1
                    l1 = l1.next
                else:
                    p.next = l2
                    l2 = l1
                    l1 = p.next.next
                p = p.next
            if not l1:
                p.next = l2
            else:
                p.next = l1
                
            return dummy.next
        
        amount = len(lists)
        interval = 1
        while interval < amount:
            for i in range(0, amount - interval, interval * 2):
                lists[i] = merge(lists[i],lists[i+interval])
            interval *= 2
        return lists[0] if amount > 0 else None

2023.09.06 AC

<iframe width="560" height="315" src="https://www.youtube.com/embed/q5a5OiGbT6Q?si=JjJmpYXQJz-Bn1Ns" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>
<br></br>

# 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[Optional[ListNode]]) -> Optional[ListNode]:
        def merge(list1: ListNode, list2: ListNode):
            dummy = ListNode()
            cur = dummy
            while list1 and list2:
                if list1.val < list2.val:
                    cur.next = list1
                    list1 = list1.next
                else:
                    cur.next = list2
                    list2 = list2.next
                cur = cur.next
            if list1:
                cur.next = list1
            else:
                cur.next = list2
            return dummy.next
        
        if len(lists) == 0: return None
        while len(lists) > 1:
            l = []
            for i in range(0,len(lists),2):
                list1 = lists[i]
                list2 = lists[i+1] if i + 1 < len(lists) else None # 如果超出就給空鏈表
                l.append(merge(list1,list2))
            lists = l
        return lists[0]