Big O Practice: Merge Two Sorted Lists

def merge_two_lists(a, b):
    dummy = ListNode()
    tail = dummy
    while a and b:
        if a.val < b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

Variables

• n - length of the first list
• m - length of the second list

Explanation

Each node from each list is visited exactly once and re-linked in place - **O(n + m)** time. We allocate only the dummy head, **O(1)** auxiliary space. (No new nodes are created; the result is woven from existing ones.)

More Big O practice problems · Today's daily problem