Q45: Merge K Sorted Lists. - DSA Patterns (Multi-Lang)

In Simple Words: Divide and conquer: Pairwise merge lists using mergeTwoLists. In round 1, merge $K$ lists into $K/2$; in round 2, $K/4$, until 1 list remains.

Time: $O(N \log K)$ | Space: $O(1)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def mergeKLists(lists: list[ListNode | None]) -> ListNode | None:
    if not lists: return None
    def merge2(l1, l2):
        dummy = ListNode(0)
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next = l1; l1 = l1.next
            else:
                tail.next = l2; l2 = l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next
    
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if (i + 1) < len(lists) else None
            merged.append(merge2(l1, l2))
        lists = merged
    return lists[0]