How do you merge k sorted lists?

Q: How do you merge k sorted lists?

**Target Audience:** Intermediate — you should know Python classes and how a singly linked list works; heaps are explained on the linked page. **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Three teachers have each marked a pile of exam papers, and each pile is already sorted by student number, smallest on top. The school office wants **one** pile, sorted by student number. Nobody wants to throw all the papers on the floor and sort them again from scratch — each pile is already in order, and that is valuable. The natural method: look at the **top paper of every

The problem

Question presented to candidate: "You are given k sorted singly linked lists. Merge them into one sorted linked list and return its head. Write it in Python, and tell me the time and space complexity in terms of k and the total number of nodes N."

What a strong answer should cover:

The baseline approaches and their costs: collect-and-sort O(N log N); merging one by one O(N·k).
The min-heap of the k current heads: pop the smallest, append it, push its next; O(N log k) time, O(k) extra space, nodes re-linked rather than copied.
Divide and conquer (pairwise merging in log k rounds) as the other O(N log k) answer, and when each is preferable.
Edge cases: empty input, empty lists inside the input, duplicates, one list.
Python specifics: heapq compares whole tuples, and ListNode objects are not comparable — push (node.val, i, node) with a unique tie-breaker i, or define __lt__; use a dummy head node.

Clarifying questions expected:

May I re-use the existing nodes, and can lists be empty?
How large are k and N, and are the lists in memory or streamed?

Code / implementation expected: Yes — a full heapq-based merge on a ListNode class in Python.

heap
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: Intermediate — you should know Python classes and how a singly linked list works; heaps are explained on the linked page.
Difficulty: Hard
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Three teachers have each marked a pile of exam papers, and each pile is already sorted by student number, smallest on top. The school office wants one pile, sorted by student number. Nobody wants to throw all the papers on the floor and sort them again from scratch — each pi

The solution is hidden so you can try first

12 min read · 11 sections

Python code

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

PythonMerge k sorted linked lists with a min-heap of the current heads

Practice

PythonOne by one vs divide and conquer vs heap: comparisons and heap size counted