Merge Two Sorted Lists

Learning goal: Recognize the merge operation as a controlled weave of two already sorted linked lists.

Core idea Each list exposes a current head node. Because both lists are sorted, the smallest node not yet used must be one of those two heads. Choose the smaller head, append it to the result, and advance only the list that supplied it. This avoids scanning values that cannot be the next answer.

Algorithm plan

• Keep pointers a and b at the current nodes of the two lists.
• Compare a.val and b.val while both pointers are non-null.
• Attach the smaller node to the result and advance its source pointer.
• Attach whichever remainder is still non-null.

Micro-example For [1,2,4] and [1,3,4], the first comparison is 1 <= 1. Take the first list's node, then compare 2 with 1.

Pitfalls

• Treating the lists as unsorted can lead to unnecessary work.
• Advancing both pointers after one choice skips a node.
• Forgetting the remainder loses the tail of one list.

Recap

• The next answer is always the smaller visible head.
• Only one input pointer advances per merge step.
• The operation can reuse existing nodes.

Learning goal: Understand how a dummy node removes special cases when building the merged list.

Core idea A result list normally needs special handling for its first node because there is no previous node to update. Create a temporary dummy node first, then always attach the chosen node after tail. The first real node becomes dummy.next, whether it came from the first list, the second list, or the only non-empty list.

Data structure model

• dummy: a fixed sentinel before the real answer.
• tail: the last node currently in the merged chain.
• a, b: the unmerged suffixes of the two inputs.
• After attaching a node, set tail = tail.next.

Micro-example Initially, dummy -> None and tail = dummy. If list1 contributes 1, the update is dummy.next = 1, then tail moves to that 1.

Pitfalls

• Returning dummy includes the sentinel in the answer.
• Reusing tail as an input pointer can disconnect the result.
• Creating new nodes is unnecessary for this problem.

Recap

• The dummy is scaffolding, not part of the returned list.
• dummy.next is the merged head.
• One invariant makes every append identical.

Learning goal: Translate the merge invariant into a short, constant-space procedure.

Core idea The merged prefix is always sorted, and tail points to its final node. While both inputs remain, the smaller current value is safe to append because every other unmerged node is at least as large as its own current head. Once either pointer becomes null, the other pointer already names a sorted remainder, so link it directly.

Algorithm plan

Create dummy and set tail = dummy
Set a and b to the two list heads
While a and b are not null:
    choose a if a.val <= b.val; otherwise choose b
    attach chosen after tail
    move tail to chosen
    advance the chosen input pointer
Attach a if it remains; otherwise attach b
Return dummy.next

Micro-example After producing 1,1,2,3,4, list1 is empty and list2 points to its final 4. One link completes the answer.

Pitfalls

• Use <= consistently if equal nodes should favor the first list.
• Save or identify the chosen node before advancing its input pointer.
• Check both pointers before reading .val.

Recap

• Compare, attach, advance: one repeated operation.
• Link the remaining suffix in one step.
• The returned chain begins at dummy.next.

Learning goal: Trace every pointer and link while merging one concrete pair of lists.

Core idea Use list1 = [1,2,4] and list2 = [1,3,4]. The visualization treats each value as an existing node and shows the next map changing as links are woven together. Equal values are resolved by taking list1 first, using the <= rule.

Pointer movement

Micro-example The links evolve as dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4. The final result is [1,1,2,3,4,4].

Pitfalls

• A comparison event should attach only one node.
• The old next links are rewired through tail; do not duplicate nodes.
• The final remainder step is part of the algorithm, not an optional cleanup.

Recap

• Follow the smaller head at each comparison.
• The merged prefix remains sorted after every attachment.
• The visualization ends at dummy.next.

Learning goal: Identify the pointer mistakes that most often break linked-list merging.

Core idea The algorithm is short, but linked-list code fails when it mishandles the first node, null pointers, or the final suffix. The dummy head is especially valuable because it eliminates the awkward question, "Is this the first result node?" Every real node follows the same attach-and-advance pattern.

Edge-case checklist

• If both lists are empty, dummy.next is null.
• If one list is empty, link the other list immediately.
• If all values in one list are smaller, the other list becomes the remainder.
• Equal values still require advancing exactly one pointer.

Micro-example For [] and [0], the loop never runs. The remainder assignment sets dummy.next to the node containing 0, so the answer is [0].

Pitfalls

• Reading a.val or b.val after that pointer became null.
• Returning the dummy instead of dummy.next.
• Detaching the remainder by overwriting a needed next pointer.

Recap

• Let null checks guard every comparison.
• Let the dummy handle the first insertion.
• Link, do not copy, the sorted remainder.

Learning goal: Explain why dummy-head merging is optimal for the required time and space bounds.

Core idea Each node is attached once and each input pointer moves only forward. Therefore, the loop performs at most n + m comparisons or attachments, where n and m are the input lengths. The algorithm stores only a few pointers; it does not allocate an array or recursion stack.

Complexity analysis

Micro-example For lengths 3 and 3, at most six nodes are processed. The result reuses those same six nodes, so extra storage stays constant.

Pitfalls

• Calling the result construction O(n + m) space when nodes are reused is incorrect.
• Counting the dummy as an input node changes neither bound.
• A recursive implementation may use O(n + m) call-stack space, unlike this iterative approach.

Recap

• Time: O(n + m).
• Extra space: O(1).
• Dummy plus two moving input pointers gives clean, optimal weaving.