AlgoMaster Logo

Merge Two Sorted Lists

Last Updated: March 29, 2026

easy
3 min read

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.

If you think about how you'd merge two sorted piles of cards by hand, the process is intuitive: look at the top card of each pile, pick the smaller one, place it on the output pile, and repeat. When one pile runs out, just move the remaining pile directly onto the output. That's exactly the algorithm here. The only wrinkle is that we're working with linked list pointers instead of arrays, so we need to carefully wire up .next pointers as we go.

Key Constraints:

  • 0 <= number of nodes <= 50 → Both lists can be empty (zero nodes). Any approach, even O(n^2), would be instant with n up to 50. Performance is not a concern here, so focus on clean, correct logic.
  • -100 <= Node.val <= 100 → Values can be negative. The comparison logic works the same regardless.
  • Both lists are sorted in non-decreasing order → This is the critical property that makes a simple merge possible. We can always compare just the current heads, because the smallest unseen element in each list is always at the front.

Approach 1: Recursive

Intuition

Here's the recursive insight: at each step, we compare the heads of the two lists. Whichever is smaller becomes the head of the merged result. Then its .next should point to whatever comes from merging the rest of that list with the other list. That's the same problem, just smaller.

The base cases are simple. If one list is empty, the answer is the other list. If both are empty, the answer is null.

This is a natural way to think about the problem, and the code is elegant. But it uses O(n) stack space due to recursion, which matters if the lists are very long.

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 recursive approach is clean but uses O(n + m) stack space. Can we do the same merge iteratively with only O(1) extra space?

Approach 2: Iterative with Dummy Node

Intuition

The idea is the same as the recursive approach: compare heads, pick the smaller one, advance that pointer. But instead of using the call stack to remember where we are, we maintain a tail pointer that tracks the end of the merged list we're building.

There's one annoying detail with linked list problems: the very first node needs special handling because there's no "previous node" to attach it to. A common trick is to create a dummy node at the start. The dummy's .next will eventually point to the real head of the merged list. This eliminates the special case for the first insertion and makes the code much cleaner.

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