AlgoMaster Logo

Merge Two Sorted Lists

easyFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We have two linked lists, each already sorted in non-decreasing order, and we need to combine them into a single sorted linked list. The key phrase is "splicing together the nodes," which means we should reuse the existing nodes rather than creating new ones.

This is the same process as merging two sorted piles of cards by hand: look at the top card of each pile, take the smaller one, place it on the output pile, and repeat. When one pile runs out, move the remaining pile directly onto the output. The difference here is that we work with linked list pointers instead of arrays, so we have to rewire .next pointers as we go rather than copy values into a new array.

Key Constraints:

  • 0 <= number of nodes <= 50 → Either or both lists can be empty, so the code must handle a null head without crashing.
  • -100 <= Node.val <= 100 → Values can be negative. The comparison logic is identical for negative and positive values, and all values fit in a 32-bit integer with no overflow risk.
  • Both lists are sorted in non-decreasing order → This is the property that makes a single linear pass possible. The smallest unmerged element across both lists is always one of the two current heads, so comparing the heads is enough to decide what comes next.

Approach 1: Recursive

Intuition

At each step, we compare the heads of the two lists. The smaller head becomes the head of the merged result, and its .next points to the result of merging the rest of that list with the other list. That subproblem has the same shape as the original, with one fewer node, which makes recursion a direct fit.

The base cases are the empty lists. If one list is empty, the answer is the other list unchanged. If both are empty, returning either one returns null.

The recursion depth equals the total number of nodes, so this uses O(n + m) stack space. That becomes a problem for long lists, which the next approach avoids.

Algorithm

  1. If list1 is null, return list2. If list2 is null, return list1.
  2. Compare the values at the heads of list1 and list2.
  3. If list1.val <= list2.val, set list1.next to the result of merging list1.next with list2. Return list1.
  4. Otherwise, set list2.next to the result of merging list1 with list2.next. Return list2.

Example Walkthrough

1Initial: compare list1[0]=1 vs list2[0]=1
null
1/6

Code

The next approach performs the same merge iteratively, using a fixed number of pointers instead of the call stack, which brings the space down to O(1).

Approach 2: Iterative with Dummy Node

Intuition

The comparison logic matches the recursive approach: compare heads, take the smaller one, advance that pointer. Instead of relying on the call stack to remember position, we keep a tail pointer at the end of the merged list we are building and append each chosen node there.

The first node of the merged list has no predecessor to attach to, which would otherwise force a special case before the loop. Allocating a dummy node up front removes that case. Every real node, including the first, is attached as tail.next, and the merged list begins at dummy.next.

Algorithm

  1. Create a dummy node. Set a tail pointer to the dummy.
  2. While both list1 and list2 are non-null:
    • Compare list1.val and list2.val.
    • Attach the smaller node to tail.next, then advance that list's pointer.
    • Advance tail to tail.next.
  3. When the loop ends, one list might still have remaining nodes. Attach whichever is non-null to tail.next.
  4. Return dummy.next (the real head of the merged list).

Example Walkthrough

1dummy -> null, tail = dummy
null
1/7

Code