LeetCode 21 · Linked List

Merge Two Sorted Lists, explained with a picture

Two sorted trains meeting at a junction.

EasyLinked List
▶ Watch it step by step

The problem

Merge two sorted linked lists into one sorted list and return its head.

Input:  1 → 2 → 4  and  1 → 3 → 4
Output: 1 → 1 → 2 → 3 → 4 → 4

Picture it

Picture two sorted trains arriving at a junction. A dispatcher looks at the front coach of each and sends the smaller one onto the main line, then repeats. A dummy coach waits on the main line first so there is always something to couple to. When one train runs out, the rest of the other is attached as is.

How to recognise it

  • You have two inputs that are already sorted and need one sorted output.
  • The smallest remaining item is always at the front of one of the two inputs, so you never need to look further in.
  • The inputs are linked lists, so the result can be built by relinking the existing nodes instead of creating new ones.
  • Building a new list from nothing invites special cases for "the first node". A dummy node (a placeholder that sits before the real head) removes them.
  • This merge step is the heart of merge sort and of Merge k Sorted Lists.

Start with brute force

Ignore that the lists are sorted: read every value, sort them, and build a fresh list.

def merge_brute(a, b):
    vals = []
    for node in (a, b):
        while node:
            vals.append(node.val)
            node = node.next
    vals.sort()
    dummy = tail = Node(0)
    for v in vals:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next

With m + n values this is O((m + n) log(m + n)) time and O(m + n) extra space. LeetCode allows only 50 nodes per list, so speed is not the issue. The waste is that it throws away the order the input already has, and it creates m + n new nodes when the problem asks you to splice the existing ones together.

From brute force to the idea

  1. Use the order you were given. Both lists are sorted, so the smallest value not yet used is the front of a or the front of b. One comparison decides the next node.
  2. Start with a dummy. dummy is a throwaway node and tail is the last node of the merged list so far. Appending is always tail.next = node, even for the very first node.
  3. Take the smaller front. If a.val <= b.val, link a and advance a; otherwise link b and advance b. Then move tail to the node just added. Using <= takes from a on ties, which keeps equal values in their original order.
  4. Attach the leftovers in one step. When one list runs out, the rest of the other is already sorted and already linked together, so tail.next = a or b finishes the job without a loop.
  5. Skip the dummy. The merged list starts at dummy.next.

This is the key idea: compare the two fronts, splice the smaller one onto the tail, and attach whatever is left at the end.

The key idea

Always take the smaller front node; a dummy head avoids special cases. O(m + n).

Python solution

def merge(a, b):
    dummy = tail = Node(0)
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO((m + n) log(m + n)): sorting all valuesO(m + n): the value list and the new nodes
Two-pointer merge (shown code)O(m + n): each loop step links one node; the leftovers are attached in O(1)O(1): one dummy node and a few references

Edge cases

  • Both lists empty: the loop never runs, tail.next = None, and the code returns None.
  • One list empty: the loop never runs and the other list is returned whole.
  • Equal values (1 → 2 → 4 and 1 → 3 → 4): returns 1 → 1 → 2 → 3 → 4 → 4, with a's 1 before b's 1.
  • All of one list smaller (1 → 2 and 5 → 6): a empties after two steps and 5 → 6 is attached in one move.
  • The inputs are changed: the original nodes are relinked, so the old lists should not be used afterwards.
  • Long lists: the loop is iterative. A recursive merge would hit Python's default recursion limit at around 1,000 nodes in total.

Common mistakes

  • Forgetting tail.next = a or b, which silently drops the rest of the longer list.
  • Forgetting tail = tail.next, so every node is written into dummy.next and overwrites the one before. For 1 → 2 and 5 → 6 the result is just 5 → 6.
  • Returning dummy instead of dummy.next, which puts an extra 0 at the front.
  • Looping while a or b without guarding None, which raises AttributeError when one list ends.
Your turn: merge without duplicates

Merge two sorted lists into one sorted list that contains each value only once. For 1 → 2 → 4 and 1 → 3 → 4 the answer is 1 → 2 → 3 → 4. Describe your approach, then write it if you like.

Compare with our answer

Keep the same merge, but run until both lists are empty and only link a node if its value differs from the current tail. The dummy has no real value, so the first node is always linked. At the end, cut tail.next, because the last linked node may still point at skipped duplicates.

def merge_unique(a, b):
    dummy = tail = Node(0)
    while a or b:
        if b is None or (a is not None and a.val <= b.val):
            node, a = a, a.next
        else:
            node, b = b, b.next
        if tail is dummy or node.val != tail.val:
            tail.next = node
            tail = node
    tail.next = None
    return dummy.next

Time O(m + n), space O(1).

A strong answer mentions: comparing with the tail's value (duplicates can come from either list), treating the dummy as "no value yet", and cutting tail.next at the end.

Check what stuck

1. Two sorted arrays of IDs, each with up to 10^6 entries, must be combined into one sorted array. Which approach fits best?

2. Why does the shown code need only O(1) extra space?

3. A learner deletes the line tail.next = a or b. What does the code return for 1 → 2 → 4 and 1 → 3 → 4?

Score 60% or more and the lesson is marked complete.