Merge two sorted linked lists

Given the head pointers of two sorted linked lists, both arranged in non-decreasing order, merge them into one sorted list and return the head of the result.

You must splice the nodes together — no value is dropped, no value is added. Every node from both inputs appears exactly once in the output, and the output stays sorted from smallest to largest.

Think of it like merging two already-sorted stacks of numbered cards into a single sorted pile: at each step you take the smaller card from the top of one stack. Because each stack is already ordered, you never have to look deeper than the top card.

Hints

· Stuck? Reveal one nudge at a time.

You have two piles that are each already sorted. What's the very first value of the merged result guaranteed to be?

You never have to look past the front of each list — the smallest remaining value is always one of the two current heads.

Build the answer behind a dummy node, and at each step link the smaller of the two heads, then advance that pointer.

Common doubts

It gives you a fixed node to append behind, so the first append is no different from the rest. You return dummy.next as the real head.

Take either one — the result stays sorted. Using <= picks the node from head1 first, which keeps the merge stable.

No. The optimal solution re-links the existing nodes, so it uses only O(1) extra space. The brute force allocates copies, which is wasteful here.

Interview follow-ups

· What an interviewer asks next.

Use a min-heap of the k current heads (pop the smallest, push its next), giving O(N log k), or merge them pairwise like the merge step of merge sort.

Yes — pick the smaller head as the start, then splice, but you'll need an explicit check for which list begins the result. The dummy node exists precisely to avoid that special case.

Fun facts

This exact two-pointer weave is the merge in merge sort — the step that makes the whole algorithm O(n log n).
The same idea scales to external sorting: databases merge sorted runs from disk that are far too big to fit in memory.

Asked at

AmazonMicrosoftGoogleAdobeMeta

Frequently Sometimes Occasionally

Example 1

Input: head1 = [5,10,15,40], head2 = [2,3,20]
Output: [2,3,5,10,15,20,40]
Interleaving the two sorted lists keeps every value in non-decreasing order.

Example 2

Input: head1 = [1,2,4], head2 = [1]
Output: [1,1,2,4]
The single node `1` from head2 slots in front of head1's `2`, and the rest follow in order.

Constraints

- 1 <= number of nodes in list1 <= 10^3 - 1 <= number of nodes in list2 <= 10^3 - 0 <= node value <= 10^5 - Both input lists are sorted in non-decreasing order.

Merging two sorted lists is the single most important warm-up for the merge step of merge sort — and a favourite interview opener because a clean answer needs only pointers, no extra array. We'll go from the obvious "collect everything and sort" all the way to the elegant one-pass weave.

Prerequisites

Before you start

· Concepts used directly in the solution.

Singly linked list traversal. Walking a list with a node = node.next loop until you hit null.

Dummy head node. A throwaway node you build the answer behind, so you never special-case the first append.

Two-pointer comparison. Advancing two cursors independently and always consuming the smaller front element.

Understand the problem

Plainly: you're given two lists that are each sorted. Produce one list containing all the same nodes, still sorted. Formally, given head1 and head2 where each list is non-decreasing, return the head of a single non-decreasing list whose multiset of values is the union (with duplicates) of both inputs.

Worked example — head1 = [5,10,15,40], head2 = [2,3,20]

head1: 5 -> 10 -> 15 -> 40
head2: 2 -> 3 -> 20

compare fronts, take smaller each step:
  2 (h2)  3 (h2)  5 (h1)  10 (h1)  15 (h1)  20 (h2)  40 (h1)
result: 2 -> 3 -> 5 -> 10 -> 15 -> 20 -> 40

Clarifying questions

Asking these before coding shows you're thinking about the contract, not just the happy path.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Are both lists guaranteed sorted in non-decreasing order?”

The whole one-pass approach depends on it — if not, you'd have to sort first.

“Can either list be empty?”

If one is empty you should return the other head untouched, so the loop must handle a null cursor.

Output shape

“Should I reuse the existing nodes or allocate fresh ones?”

Reusing (splicing) is O(1) extra space; allocating copies is simpler but wasteful.

“Are duplicate values allowed and kept?”

Yes — merging preserves every node, so equal values sit next to each other.

Constraints and scale

“What is the maximum combined length?”

Up to about 2000 nodes here — well within a single linear pass, no need for anything fancier.

The ideal opening - say it like this

Before I code, let me confirm the guarantees.

First, both lists are already sorted non-decreasing - that lets me merge in one pass.

And I'll splice the existing nodes rather than allocate new ones, keeping extra space constant.

Key observations

1Aha

The smallest unused value is always at a front

Each list is sorted, so its smallest remaining value sits at its current head. The overall smallest of what's left must therefore be one of the two heads — never buried in the middle. That's why comparing just the two fronts is enough.

2Aha

A dummy head removes the first-node special case

Without a placeholder you'd need an if result is empty check on every append. Building behind a dummy node lets every step do the same tail.next = chosen; tail = tail.next, and you return dummy.next at the end.

dummy -> [ ] ...tail grows here
return dummy.next as the real head

3Aha

When one list runs out, attach the rest in O(1)

Once either cursor hits null, the other list is already sorted and entirely larger-or-equal to what you've placed. You can hang its whole remainder off the tail with a single pointer assignment — no more comparisons needed.

Brute force vs optimal

	Brute force (collect + sort)	Optimal (one-pass weave)
Time	O((m+n) log(m+n))	O(m + n)
Space	O(m + n)	O(1) extra
Uses sortedness?

The full code for both lives in the Approaches selector below.

Summary

Key takeaway

When two inputs are already sorted, you never need to re-sort — a two-pointer weave that always consumes the smaller front merges them in linear time and constant extra space. This is exactly the merge in merge sort.

dummy = new node; tail = dummy
while head1 and head2:
    if head1.val <= head2.val: tail.next = head1; head1 = head1.next
    else:                      tail.next = head2; head2 = head2.next
    tail = tail.next
tail.next = head1 if head1 else head2
return dummy.next