Merge Two Sorted Lists: The Fundamental Merge Operation

Merge Two Sorted Lists is LeetCode problem 21 and one of the most important easy problems to master. It is the building block that powers merge sort, merge k sorted lists, and a whole family of problems that combine sorted sequences. If you can write this from memory, you unlock a lot of harder problems for free.

The problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list by splicing together the nodes of the two input lists. Return the head of the merged linked list.

Example: list1 = [1, 2, 4], list2 = [1, 3, 4]. The merged result is [1, 1, 2, 3, 4, 4].

The approach: dummy head and two pointers

The idea is simple. You maintain a pointer into each list and a pointer to the tail of the result. At each step, compare the two heads. Whichever is smaller (or equal), attach it to the result and advance that pointer. When one list runs out, attach the remainder of the other list.

There is one small trick that makes the code clean: use a dummy head node. Without it, you need special logic to handle the very first node (since there is no "previous node" to attach to). The dummy node acts as a placeholder. You build the result after it, then return dummy.next at the end.

Three pointers:

• p1 walks through list1
• p2 walks through list2
• curr tracks the tail of the merged result

At each step:

1. If p1.val is less than or equal to p2.val, set curr.next = p1 and advance p1.
2. Otherwise, set curr.next = p2 and advance p2.
3. Advance curr to curr.next.
4. When either list is exhausted, attach the remaining nodes from the other list.

Visual walkthrough

Let's trace through list1 = [1, 2, 4] and list2 = [1, 3, 4]. Watch the two pointers (p1 in amber, p2 in green) as they advance through each list.

Notice how in step 6, when p1 is exhausted, you just point curr.next to the remaining nodes of list2. No copying needed. The remaining nodes are already sorted and already linked together.

The code

Here is the Python solution:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_two_lists(list1, list2):
    dummy = ListNode(0)
    curr = dummy

    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr = curr.next

    curr.next = list1 if list1 else list2
    return dummy.next

The key details:

• while list1 and list2 runs as long as both lists have nodes remaining. The moment one runs out, the loop exits.
• list1.val <= list2.val uses <= to maintain stability (nodes from list1 come first when values are equal), though either choice produces a valid sorted result.
• curr.next = list1 if list1 else list2 handles the cleanup. Whichever list still has nodes gets attached directly. No loop needed since those nodes are already linked.
• dummy.next skips past the placeholder and returns the real head of the merged list.

Complexity analysis

This is optimal. You must examine every node at least once to determine its position, so O(n + m) is a lower bound. And since you splice existing nodes rather than creating new ones, no extra space is needed beyond the pointers.

The building blocks

This problem is built from two core building blocks that appear in dozens of other problems.

Two-pointer merge

You have two sorted sequences and a pointer into each one. At each step, compare the current elements, pick the one that belongs next, and advance that pointer. This is the merge step from merge sort, and it is one of the most reusable patterns in algorithm design.

This same building block shows up in:

• Merge Sorted Array (LeetCode 88) applies the same logic to arrays, filling from the back for in-place operation.
• Merge K Sorted Lists (LeetCode 23) extends it using a heap or divide-and-conquer to handle k inputs.
• Intersection of Two Arrays II (LeetCode 350) uses the merge walk but only keeps matching elements.

Dummy head technique

When building a linked list node by node, create a dummy sentinel node at the start. Append new nodes after it. Return dummy.next when done. This avoids special-casing the first insertion and eliminates null-check bugs.

You will see the dummy head in nearly every linked list construction problem: merge lists, partition lists, add two numbers, and more. Once this technique is automatic, you stop thinking about edge cases at the head of the list entirely.

Edge cases to watch for

• One list is empty. If list1 is None, the while loop never runs and you return list2 directly (and vice versa). The curr.next = list1 if list1 else list2 line handles this.
• Both lists are empty. Both are None, the loop never runs, curr.next is set to None, and dummy.next returns None.
• One element each. list1 = [1], list2 = [2]. One comparison, one attachment, then the cleanup line attaches the remaining node.
• All elements from one list are smaller. For example, list1 = [1, 2, 3], list2 = [7, 8, 9]. The loop picks all of list1 first, then attaches all of list2 in the cleanup.
• Duplicate values across lists. list1 = [1, 1], list2 = [1, 1]. The <= comparison handles this cleanly, alternating picks between the two lists.

From understanding to recall

This is one of those problems where the solution is short enough to feel trivial once you see it. That is exactly what makes it dangerous. You read it, understand it, and assume you will remember it. But under interview pressure, the details slip. Do you use <= or <? Where does the dummy node go? What happens when one list runs out?

The only way to make these details automatic is repetition. Not re-reading the solution, but typing it from scratch. Spaced repetition schedules the practice at exactly the right intervals so you retain it with minimal time invested. After a few reps, the dummy head and the two-pointer merge become muscle memory.

Related posts

• Merge Sorted Array - The same two-pointer merge applied to arrays, with the backwards fill trick for in-place operation
• Merge K Sorted Lists - Scaling the merge to k lists using a min heap or divide and conquer

---

Visual Learner? Explore how linked list operations work with our Linked List Interactive Visualization.