You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list and return the head. Use a dummy node and two pointers. At each step, pick the smaller node and advance that pointer. When one list is exhausted, append the rest of the other.

The step-through player is coming for this one. Two Sum has the full animation today; the rest are being authored in the admin.

Pythontime O(m+n) · space O(1)

def mergeTwoLists(list1, list2):
    dummy = ListNode(0)
    curr = dummy
    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr = curr.next
    curr.next = list1 or list2
    return dummy.next

Next upInvert Binary Tree

Two Sum is free. Enroll to unlock every visualization and save where you stopped.Enroll free

Watch the video walkthrough