Merging Sorted Lists

July 2026 · 21 min read

Merging two sorted lists is the quiet workhorse of linked-list algorithms. It is the combine step of merge sort (the subject of the next post), the core of k-way merge in external sorting, and a favourite interview warm-up precisely because a candidate who writes it cleanly reveals they understand dummy heads, tail pointers, and the difference between relinking and copying. Do it on arrays and you allocate an output buffer; do it on lists and you allocate nothing — you just re-thread pointers through nodes that already exist. That distinction runs through this entire post.

The Two-Way Merge, Done Right

The clean version uses a dummy head so the first node is not a special case, and a tail pointer so each append is O(1) instead of a walk to the end:

ListNode* mergeTwo(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && 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 ? a : b;        // attach the whole remaining run in O(1)
    return dummy.next;
}

Three details carry the whole method:

• The tail pointer keeps append at O(1). tail always points at the last node of the output so far, so hooking on the next winner is a single write — never a re-scan. Forget it and you have accidentally written an O(n²) merge.
• Attach the remainder, do not loop it. When one list empties, the other is already sorted and already linked, so a single tail->next = a ? a : b splices the entire rest on in O(1). Copying element by element here is the array habit people carry over — on a list it is pure waste.
• Stability lives in one character. Using <= (not <) means that when the two heads are equal, the element from a is taken first, so equal keys keep their original relative order. That is what makes merge sort built on this a stable sort.

The loop rests on a single invariant worth stating aloud: at the top of every iteration, tail points at the last node of a correctly merged prefix, and every node still reachable from a or b has a value at least tail->val. Each iteration preserves it by appending the smaller of the two heads, and when the loop ends one list is empty, so the remaining sorted run is already ≥ everything emitted and can be attached wholesale. That invariant is why the merge is correct, not merely plausible.

Watch It Merge

Merging 1 → 3 → 5 with 2 → 3 → 6. Each step compares the two current heads, takes the smaller (ties go to a), and advances tail.

The same run as a table, tracking where tail lands after every step:

Result: 1 → 2 → 3 → 3 → 5 → 6. The two 3s appear in a-before-b order, which is the stability guarantee in action. Every step is one comparison and O(1) pointer work, so the merge is O(n + m) time.

The No-Dummy Version and Its Ugly Prologue

You can merge without a dummy, and it is worth writing once to appreciate what the dummy buys you. Without it, you must decide the head separately — because until you have picked the first node there is no tail to hook onto:

ListNode* mergeNoDummy(ListNode* a, ListNode* b) {
    if (!a) return b;
    if (!b) return a;
    ListNode* head;                          // the prologue: pick the head by hand
    if (a->val <= b->val) { head = a; a = a->next; }
    else                  { head = b; b = b->next; }
    ListNode* tail = head;
    while (a && 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 ? a : b;
    return head;
}

That four-line prologue — two null checks and a hand-picked head — is exactly the special-casing the dummy eliminates. This is also the honest "merge in place into the first list" answer: no dummy node is allocated, every output node is one of the original inputs, and the routine returns whichever real node became the head. Same O(n + m) time, O(1) space; just more surface area for an off-by-one.

Why This Is O(1) Extra Space

Merging two sorted arrays famously needs an output array of size n + m, because you cannot overwrite input slots you have not yet read. Lists have no such constraint. Each node already carries its own next field, so merging is nothing but choosing, for each existing node, which node comes after it. No buffer, no copies, no moves of the payload — only pointer writes.

The Recursive Merge

Because a merge of two lists is "take the smaller head, then merge the rest", it has a naturally recursive shape:

ListNode* mergeRec(ListNode* a, ListNode* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->val <= b->val) { a->next = mergeRec(a->next, b); return a; }
    else                  { b->next = mergeRec(a, b->next); return b; }
}

It is elegant and it is stable, but be clear-eyed about the cost: the recursion depth is O(n + m), one frame per node consumed, because it is not tail-recursive in a way most compilers will optimise. On two lists of a hundred thousand nodes each, that is 200,000 stack frames — a stack overflow waiting to happen. The iterative version has O(1) space and no such ceiling. Prefer the loop in production; keep the recursion for the insight and for the recursion post.

Merging k Sorted Lists

Now the real problem (LeetCode 23). You have k sorted lists holding N nodes in total. There are three standard strategies, and the gap between the worst and the best is large.

1. Sequential pairwise — O(kN)

Fold the lists left to right: merge list 0 with 1, that result with 2, and so on.

ListNode* mergeKSequential(std::vector<ListNode*>& lists) {
    ListNode* acc = nullptr;
    for (ListNode* l : lists) acc = mergeTwo(acc, l);
    return acc;
}

The trap is that the accumulator keeps growing and is re-walked every time. After folding in i lists the accumulator holds about iN/k nodes, and the next merge touches all of them. Summing i from 1 to k gives N/k · k(k+1)/2 = N(k+1)/2, i.e. O(kN). For large k this is quadratic-in-k waste.

2. Min-heap of the k heads — O(N log k)

Keep a priority queue of the current head of every list; repeatedly pop the global minimum and push its successor. The heap never holds more than k nodes, so each of the N pops and pushes costs log k.

struct Cmp {
    bool operator()(ListNode* a, ListNode* b) const { return a->val > b->val; }  // min-heap
};

ListNode* mergeKHeap(std::vector<ListNode*>& lists) {
    std::priority_queue<ListNode*, std::vector<ListNode*>, Cmp> pq;
    for (ListNode* l : lists) if (l) pq.push(l);
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!pq.empty()) {
        ListNode* node = pq.top(); pq.pop();
        tail->next = node;
        tail = node;
        if (node->next) pq.push(node->next);
    }
    tail->next = nullptr;
    return dummy.next;
}

This is O(N log k) time and O(k) extra space for the heap. The custom comparator returns a->val > b->val because std::priority_queue is a max-heap by default, and flipping the comparison turns it into the min-heap we want.

3. Divide and conquer — O(N log k)

Pair the lists up and merge in a tournament: k lists become k/2 after one round, k/4 after two, and so on for log k rounds. Every round touches all N nodes once, so the total is N log k.

ListNode* mergeKDivide(std::vector<ListNode*>& lists, int lo, int hi) {
    if (lo > hi) return nullptr;
    if (lo == hi) return lists[lo];
    int mid = lo + (hi - lo) / 2;
    ListNode* left  = mergeKDivide(lists, lo, mid);
    ListNode* right = mergeKDivide(lists, mid + 1, hi);
    return mergeTwo(left, right);
}

Think about the recursion tree. It has log₂ k levels, and although the merges near the root operate on long lists while those near the leaves operate on short ones, every level in total inspects each of the N nodes exactly once — a node participates in one merge per level as its run climbs the tree. So the work per level is Θ(N) and there are log k levels, giving O(N log k). Contrast that with sequential folding, which is really an unbalanced tree of depth k: the same node gets re-copied on every level it survives, and the levels number k instead of log k. Balancing the tree is the entire improvement.

In an interview, reach for divide and conquer: it hits the optimal O(N log k), needs no auxiliary data structure beyond the recursion stack, and reuses the two-way merge you already wrote. The heap is the better answer when the lists are not all available up front (a true streaming k-way merge) or when k is enormous.

Doubly Linked and Circular Variants

Two sorted doubly linked lists. The logic is identical, but every forward link now needs a matching prev, and you must fix the head and tail prev at the boundaries:

DNode* mergeDoubly(DNode* a, DNode* b) {
    DNode dummy(0);
    DNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a->prev = tail; a = a->next; }
        else                  { tail->next = b; b->prev = tail; b = b->next; }
        tail = tail->next;
    }
    DNode* rest = a ? a : b;
    tail->next = rest;
    if (rest) rest->prev = tail;
    DNode* head = dummy.next;
    if (head) head->prev = nullptr;    // the real head has no predecessor
    return head;
}

A sorted list into a sorted circular list. The cleanest approach is break, merge, reclose: cut the circular list at its wrap-around edge to get a plain sorted list, run the ordinary two-way merge, then re-link the last node back to the new head. Trying to splice into a live circle node by node forces you to special-case the insertion that becomes the new minimum (it moves the "start"), so linearising first is both simpler and less error-prone. See Circular Linked Lists for the break-and-reclose mechanics.

Concretely: if you hold a pointer tail to the last node of the circular list (the one whose next is the head), set tail->next = nullptr to linearise, merge with the incoming sorted list to get a new head h, walk to the new last node, and close the ring with last->next = h. If instead you are only given some arbitrary node on the circle — as in "insert into a sorted circular list" (LeetCode 708) — you first walk the ring once to find the point where value wraps from maximum back to minimum, and treat that boundary as the break. Either way the merge itself is the same O(n + m) two-way merge; only the framing around it changes. The one edge case to guard is a uniform circle where every value is identical: there is no wrap boundary, so any node is a valid insertion point.

Check Yourself

Six situations about merging. Pick the statement that is actually correct.

Practice

• LeetCode 21 — Merge Two Sorted Lists dummy dummy head, tail pointer, attach the remainder in one write.
• LeetCode 23 — Merge k Sorted Lists k-way divide-and-conquer or a min-heap for O(N log k).
• LeetCode 148 — Sort List merge sort split with fast/slow, then merge; the merge here is the combine step.
• LeetCode 1669 — Merge In Between Linked Lists splice O(1) remainder attach is the whole trick.
• LeetCode 2181 — Merge Nodes in Between Zeros relink build the result by re-threading, no new nodes.