cf.completefrontend
LINKED LISTS · CORE

Merging sorted linked lists

Combine two sorted linked lists into one sorted list by repeatedly taking the smaller front node.

Time O(n + m)Space O(1)3 practice problemsStep-through picture

The idea

You have two linked lists, each already sorted from smallest to largest. You want one sorted list with every node from both. Because each list is sorted, the smallest node overall must be at the front of one of them. Take the smaller of the two front nodes, attach it to the answer, and repeat.

The answer is built by relinking the existing nodes, not by copying values. A tail pointer marks the last node of the answer so far, and each chosen node is hooked on after it. A dummy node in front of the answer means the first node needs no special case.

When one list runs out, the other one is already sorted and every node in it is at least as big as everything taken so far, so you attach the whole rest in one step.

An everyday example

Merging two sorted stacks of exam papers

Two teachers each hand you a pile of exam papers sorted by student number, lowest on top. You want one sorted pile. You look at the top paper of each pile, put the lower number face down on your new pile, and repeat. When one pile is empty, you put the whole other pile on top at once, because it is already in order.

How the example maps to the code
In the exampleIn the code
The two sorted pileslists a and b
The top paper of each pilea.val and b.val
The top of your new piletail
Moving the lower paper overtail.next = a; a = a.next
Dropping the leftover pile on at oncetail.next = a !== null ? a : b

From the slow way to merging sorted linked lists

  1. Start with the obvious way: walk both lists, copy every value into one array, sort the array, and build a new list from it. That costs O((n + m) log(n + m)) time for the sort, O(n + m) extra memory, and new nodes, and it ignores the most useful fact we have: each list is already sorted.
  2. Sorted means the front node of each list is the smallest node still in that list. So the smallest node left anywhere must be one of the two front nodes. One comparison, a.val <= b.val, tells you which node comes next in the answer. No other node needs to be looked at.
  3. To build the answer without copying, keep a tail pointer at its last node and hook each chosen node on with tail.next, then move tail forward. A dummy node at the very start means the answer is never empty, so attaching the first node is no different from attaching any other.
  4. When one list runs out, every node left in the other is at least as big as everything already taken, and it is already sorted. So one link, tail.next = a !== null ? a : b, attaches all of it. That loop is merging sorted linked lists.

How it works

  1. Make a dummy node and set tail = dummy. The answer will hang off dummy.next.
  2. While both a and b have nodes, compare a.val and b.val.
  3. Attach the smaller node after tail and move that list forward. On a tie, take from a so equal values keep their order.
  4. Move tail to the node just attached.
  5. When one list is empty, attach the other list's remaining nodes in one step.
  6. Return dummy.next.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function mergeLists(a, b) {
  2. const dummy = new ListNode(0);
  3. let tail = dummy;
  4. while (a !== null && b !== null) {
  5. if (a.val <= b.val) {
  6. tail.next = a;
  7. a = a.next;
  8. } else {
  9. tail.next = b;
  10. b = b.next;
  11. }
  12. tail = tail.next;
  13. }
  14. tail.next = a !== null ? a : b;
  15. return dummy.next;
  16. }

How fast it is

TimeO(n + m)
Extra memoryO(1)

Each loop moves one node into the answer, and the leftover list is attached in one step. The nodes are relinked, not copied.

  • Best caseO(min(n, m))

    Every node of the shorter list is smaller than the first node of the longer one, like 1 -> 2 -> 3 and 10 -> 20 -> 30 -> 40. The loop runs 3 times and the rest is attached with one link.

  • Average caseO(n + m)

    Values from the two lists mix, so most nodes are taken one by one through a comparison.

  • Worst caseO(n + m)

    The values alternate perfectly, like 1 -> 3 -> 5 and 2 -> 4 -> 6. The loop runs n + m - 1 = 5 times and only the last node is attached as a leftover.

Common mistakes

  • Forgetting to attach the leftover list after the loop, which drops the largest values.
  • Forgetting tail = tail.next, so every new node overwrites the same link and the answer keeps only the last one.
  • Making new nodes for every value when the task says to reuse the existing ones. It works but uses O(n + m) extra memory.
  • Merging k lists one at a time into one growing list, which makes the early nodes get walked over again and again.

When to use it

Look for these clues in a problem:

  • Two or more inputs are linked lists that are already sorted.
  • The answer must be sorted and contain every node from the inputs.
  • You are sorting a linked list with merge sort and need the merge step.
  • The task asks to relink nodes rather than create new ones.

Check yourself

Answer each one in your head first, then open it.

Why is it safe to attach the whole leftover list with one link?

It is already sorted, and every node in it is at least as big as the last node taken. So no node in it needs to be compared with anything.

What happens if you forget tail = tail.next?

Every chosen node is hooked onto the same tail, so each attach overwrites the last one. The answer ends up holding only the last node chosen plus the leftover list.

At most how many comparisons does merging lists of 3 and 5 nodes take?

7, which is 3 + 5 - 1. The loop stops when one list is empty, and at that point the other still has at least one node.

Why use <= instead of <?

On ties <= takes a's node first, so equal values keep the order of the two inputs. That makes the merge stable.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule, true at the top of every loop: the chain from dummy.next to tail is sorted, it holds exactly the nodes taken so far, and every node still in a or b is at least tail.val. At the start the chain is empty, so the rule holds.

Each step keeps the rule. Because both lists are sorted, a's front is the smallest node left in a and b's front is the smallest left in b. The smaller of the two is the smallest node left anywhere, so hooking it after tail keeps the chain sorted, and everything still waiting is at least as big as it.

The loop ends because each pass moves a or b one node forward, so after at most n + m - 1 passes one of them is null. Then the other list is sorted and, by the rule, every node in it is at least tail.val, so attaching it whole keeps the answer sorted and complete.

Ties go to a because of <=. So if two nodes have equal values, the one from a comes first, and nodes from the same list never change their order. A merge with this property is called stable, which matters when the nodes carry more than a number, such as messages sorted by time.

Going deeper

3 more ideas

Why the smaller front node is always right

Both lists are sorted, so a's front node is the smallest node left in a, and b's front node is the smallest left in b. The smaller of the two is therefore the smallest node left anywhere, which is exactly the node that belongs next in the answer.

Cost

Each loop attaches one node, so merging lists of lengths n and m takes O(n + m) time. No new nodes are made apart from dummy, so the extra space is O(1).

Merging more than two lists

To merge k sorted lists, merge them in pairs: list 1 with 2, 3 with 4, and so on, then merge the results in pairs again. Each round halves the number of lists, so the total work is O(N log k) for N nodes. Merging them one by one into a growing answer is slower, O(N k). A heap of the k front nodes is the other common way.

Work it by hand

Every step in a table, with why

Merge two four-node lists that share the value 5, so the trace shows how ties are broken and how the leftover list is attached.

a = 2 -> 5 -> 5 -> 9, b = 1 -> 5 -> 12 -> 14

Stepaba.val <= b.valTakenAnswer so farWhy
121false1 from b11 is smaller, so it is hooked onto dummy and b moves to its 5.
225true2 from a1 -> 22 is smaller, so a gives up its front node and moves to its first 5.
355true5 from a1 -> 2 -> 5A tie. <= takes from a, so equal values keep a's copies before b's.
455true5 from a1 -> 2 -> 5 -> 5Another tie with b's 5. a's second 5 goes first for the same reason.
595false5 from b1 -> 2 -> 5 -> 5 -> 5Now b's 5 is smaller than 9, so it is taken.
6912true9 from a1 -> 2 -> 5 -> 5 -> 5 -> 99 is taken and a becomes null, so the loop condition fails.
7null12-rest of b... -> 9 -> 12 -> 14a is empty, so tail.next = b attaches 12 -> 14 in one step without comparing them.

It returns 1 -> 2 -> 5 -> 5 -> 5 -> 9 -> 12 -> 14: all 8 nodes after 6 comparisons. The last two nodes were attached with a single link.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Merging sorted linked listsO(n + m)O(1)Both inputs are already sorted and you can relink their nodes.
Collect all values, sort, rebuildO(n log n)O(n)The inputs aren't sorted, or you need brand-new nodes and don't care about speed.
Recursive mergeO(n + m)O(n + m)The lists are short and you prefer the shortest code.

Extra memory: O(1): one dummy node and the tail pointer. The existing nodes are relinked, not copied. A recursive merge uses O(n + m) stack space instead.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Merging sorted linked lists and the other approaches, on a scale where each line up is 10 times more steps.
  • Merging sorted linked lists, Recursive merge O(n + m)
  • Collect all values, sort, rebuild O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Merging sorted linked lists202,0002 million
Collect all values, sort, rebuild339,96620 million
Recursive merge202,0002 million

Inputs that need care

5 tricky inputs
One list is empty: a = null
The loop never runs, and tail.next = b attaches all of b. The function returns b itself.
Both lists are empty
The loop never runs, tail.next is set to null, and the function returns null.
Equal values in both lists
<= takes a's node first. Use < only if the task wants b's copies first; either way the result is sorted.
Very different lengths: one node against 1,000 nodes
At most one comparison per node of the short list, then one link attaches the rest of the long list. The length difference costs nothing extra.
An input list that isn't sorted, like a = 4 -> 1
The code doesn't check. The result contains every node but may not be sorted: with b = 2 -> 3, it returns 2 -> 3 -> 4 -> 1. Merge only sorted input, or sort first.

Variations and follow-ups

Twists interviewers add

Merge k sorted lists

Merge the lists in pairs, then merge the results in pairs, until one list is left. Each round touches every node once and halves the number of lists, so it takes O(N log k) for N nodes in total. A heap of the k front nodes gives the same time and picks the smallest front each step.

Merge sort on a linked list

Split the list at its middle with fast and slow pointers, sort each half the same way, and merge the two sorted halves with this loop. It sorts a linked list in O(n log n) time without copying it into an array.

Recursive merge

Return the smaller front node after setting its next to the merge of the rest. It needs no dummy or tail, but it uses one stack frame per node taken, which is O(n + m) space.

Merge and drop duplicates

Before hooking a node on, check whether its value equals tail.val. If it does, skip it instead of attaching it. The answer then holds each value once, still in sorted order.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "two sorted lists", "combine into one sorted list", or a merge sort on a linked list. Also from "merge k sorted lists", which builds on this loop.
  • Explain the one-line reason out loud: "the smallest node left must be one of the two fronts, because both lists are sorted". Then mention the dummy node so the first attach is not special.
  • Test by hand: one empty list, both empty, and lists with equal values. Check that the leftover list is attached and that tail moves every time.
  • Expect the follow-up "what about k lists?". Answer with pairwise merging or a heap for O(N log k), and explain why merging one list at a time into a growing answer is O(N k).

Where frontend code uses it

The same idea in real UI code
  • A chat or activity feed that loads older messages from two sources (for example, local cache and server) merges two time-sorted lists into one timeline.
  • Merge sort is a common stable sort, and Array.prototype.sort must be stable in modern JavaScript; V8 uses TimSort, which is built on merging sorted runs.
  • Combining sorted change lists, such as edits from two collaborators ordered by timestamp, uses the same take-the-smaller-front step.

Related algorithms