Merge Two Sorted Lists (LeetCode 21)

The problem

You get the heads of two linked lists, each already sorted in non-decreasing order. Splice their nodes together into one sorted list and return its head. Reuse the existing nodes; don’t copy values into new ones.

Input:  a = 1 -> 2 -> 4
        b = 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

At every step the smaller of the two front nodes goes next, which keeps the result sorted.

How to think about it

Start with brute force. Pour every value from both lists into an array, sort it, and build a new list. That is O((m + n) log(m + n)) time and O(m + n) space, and it throws away the fact that both inputs are already sorted.

The key insight: the smallest remaining node is always at the front of one of the two lists. So you never need to look further than the two heads. Compare them, take the smaller, advance that list, repeat. This is the merge step of merge sort, done with pointers instead of array indices.

A dummy head removes the special case. Without it you’d need an if to decide which node becomes the real head. With a throwaway ListNode() in front, the “result so far” always has a last node, tail, and every step is the same: tail.next = smaller; tail = tail.next. Return dummy.next at the end.

When one list runs out, stop comparing. The other list is already sorted and every node in it is at least as large as tail. Attach the whole remainder in one move: tail.next = a or b.

Which pattern is this? Linked-list pointer rewiring with a dummy head. The tell is “build or splice a list where the head might change”.

Approach

1. Create a dummy node d and set tail = d.
2. While both a and b have nodes:
   • if a.val <= b.val, attach a and advance a; otherwise attach b and advance b,
   • move tail to the node just attached.
3. Attach whichever list still has nodes: tail.next = a or b.
4. Return d.next.

Solution

class ListNode:                                   # LeetCode's node type
    def __init__(self, val=0, next=None):
        self.val = val; self.next = next

def merge_two(a, b):
    d = ListNode(); tail = d                      # dummy head: no special case for the first node
    while a and b:
        if a.val <= b.val: tail.next = a; a = a.next   # <= keeps equal values stable
        else: tail.next = b; b = b.next
        tail = tail.next
    tail.next = a or b                            # one list is empty: attach the rest
    return d.next
# merge_two([1,2,4], [1,3,4]) -> [1,1,2,3,4,4]

Dry run

On a = 1 -> 2 -> 4, b = 1 -> 3 -> 4:

Result: 1 -> 1 -> 2 -> 3 -> 4 -> 4.

Complexity

• Time: O(m + n). Each loop iteration attaches one node, and the final attach is O(1).
• Space: O(1). Only the dummy node and a few pointers. Nodes are re-linked, not copied. A recursive merge is O(m + n) stack space.

Edge cases and pitfalls

• One or both lists empty. The loop is skipped and tail.next = a or b returns the other list (or None).
• Equal values. <= takes from a first. Either choice is correct; <= keeps it stable.
• Forgetting to advance tail. Every new node then overwrites d.next and you lose the result.
• Looping to attach the leftovers one by one. Not wrong, but needless: the remainder is already a linked, sorted chain.
• Returning d instead of d.next puts a stray 0 at the front.

Related problems

• Merge k Sorted Lists (LeetCode 23): the same merge, with a heap choosing among k heads.
• Add Two Numbers (LeetCode 2): walks two lists in step with the same dummy-head plus tail trick.
• Squares of a Sorted Array (LeetCode 977): the same “compare two fronts, take the better one” merge, on an array.