How do you merge two sorted linked lists? | Interview Question

Q: How do you merge two sorted linked lists?

**Target Audience:** Beginners preparing for coding interviews — no prior algorithms knowledge assumed **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First Two teachers have each sorted their class's exam papers by score, lowest on top. The head teacher wants one pile for the whole year, still sorted. Nobody re-sorts 60 papers from scratch. Instead you put the two piles side by side, look at the two top papers, move the lower score onto the new pile, and repeat. When one pile is empty, you lift the whole other pile onto the new one in one go, because it is already in order. That is merging two sorted linked lists. The piles are the lists, the top paper

The problem

Question presented to candidate: "You are given the heads of two linked lists, each already sorted in ascending order. Merge them into one sorted list by splicing the existing nodes together, and return its head. Please write it in Python."

What a strong answer should cover:

The idea: the smallest remaining value is always at the front of one of the two lists, so repeatedly take the smaller front node.
A dummy (sentinel) node and a tail pointer, which remove the special case for the first node.
Attaching the leftover list in one step when the other runs out.
O(m + n) time and O(1) extra space for the loop; the recursive version uses O(m + n) stack.
Stability: using <= so equal values keep list a first.
Python specifics: is None checks, <= for stability, why heapq.merge does not apply to node objects, and the recursion limit for the recursive version.

Clarifying questions expected:

"Can I reuse the input nodes, or must the original lists stay intact?"
"Are there duplicates, and if so should ties come from the first list?"

Code / implementation expected: Yes — a Python merge_two_lists(a, b) with a dummy node, plus the recursive version if time allows.

linked-list

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no prior algorithms knowledge assumed Difficulty: Easy Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

Two teachers have each sorted their class's exam papers by score, lowest on top. The head teacher wants one pile for the whole year, still sorted. Nobody re-sorts 60 papers from scratch. Instead you put the two piles side by side, look at the two top papers, move the lower score onto the new pile, and repeat. When one pile is empty, you lift the whole other pile onto the new one in one go, because it is

The solution is hidden so you can try first

4 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonDummy-node merge on normal and edge-case inputs

Practice

PythonStability, the recursive version, and counting comparisons

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.