Q38: Merge Two Sorted Lists. - DSA Patterns (Multi-Lang)

In Simple Words: Use a dummy head node. Compare l1.val and l2.val, splice the smaller node into tail.next, and advance that list. Append remaining non-empty list.

Time: $O(N + M)$ | Space: $O(1)$

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

Switch tabs or choose All

def mergeTwoLists(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
    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 if l1 else l2
    return dummy.next