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
- Use the order you were given. Both lists are sorted, so the smallest value not yet used is the front of
aor the front ofb. One comparison decides the next node. - Start with a dummy.
dummyis a throwaway node andtailis the last node of the merged list so far. Appending is alwaystail.next = node, even for the very first node. - Take the smaller front. If
a.val <= b.val, linkaand advancea; otherwise linkband advanceb. Then movetailto the node just added. Using<=takes fromaon ties, which keeps equal values in their original order. - 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 bfinishes the job without a loop. - 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.nextIn 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O((m + n) log(m + n)): sorting all values | O(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 returnsNone. - One list empty: the loop never runs and the other list is returned whole.
- Equal values (
1 → 2 → 4and1 → 3 → 4): returns1 → 1 → 2 → 3 → 4 → 4, witha's 1 beforeb's 1. - All of one list smaller (
1 → 2and5 → 6):aempties after two steps and5 → 6is 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 intodummy.nextand overwrites the one before. For1 → 2and5 → 6the result is just5 → 6. - Returning
dummyinstead ofdummy.next, which puts an extra 0 at the front. - Looping
while a or bwithout guardingNone, which raisesAttributeErrorwhen one list ends.
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.
1. Two sorted arrays of IDs, each with up to 10^6 entries, must be combined into one sorted array. Which approach fits best?
The inputs are sorted, so comparing the two fronts gives each next value in O(1): O(m + n) overall. Sorting or a heap costs O((m + n) log(m + n)), and inserting into the middle of an array shifts elements, O(m · n) in the worst case.
2. Why does the shown code need only O(1) extra space?
The original nodes are spliced together by changing next links; no copies are made. Values are never swapped and nothing is freed.
3. A learner deletes the line tail.next = a or b. What does the code return for 1 → 2 → 4 and 1 → 3 → 4?
The loop takes a's 4 (ties go to a), and a becomes empty. tail is that 4, whose next is None, so b's 4 is never attached.
Score 60% or more and the lesson is marked complete.