Merge Two Sorted Lists

Signal

Combining two already-sorted sequences into one sorted sequence, without extra scratch space, is a dummy-head-and-splice job — you never allocate new nodes, you just re-point next pointers as you walk both lists in lockstep.

Approach

Create a throwaway dummy node so the merged list always has a stable place to hang its first real node — this avoids a special case for "which list starts first". Keep a tail pointer at the end of the merged list so far. At each step, compare the two lists' current nodes, splice the smaller one onto tail.next, and advance both tail and that list's pointer. When one list runs out, splice the remainder of the other list on directly.

Skeleton

dummy = Node()
tail = dummy
while list1 and list2:
    if list1.val <= list2.val:
        tail.next, list1 = list1, list1.next
    else:
        tail.next, list2 = list2, list2.next
    tail = tail.next
tail.next = list1 or list2
return dummy.next

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def merge_two_lists(list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
    dummy = ListNode()
    tail = dummy

    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next

    tail.next = list1 if list1 else list2
    return dummy.next

Complexity

O(n + m) time — each node from both lists is visited exactly once. O(1) space — no new nodes allocated, just re-linked existing ones.

Pitfalls

• Allocating brand-new nodes instead of re-linking the existing ones works but wastes O(n + m) space the interviewer likely wants you to avoid.
• Forgetting the dummy head and trying to special-case "which list is the initial head" adds bug surface for no benefit.
• Not attaching the leftover tail (list1 or list2) after the loop silently drops the remainder of the longer list.