Merge k Sorted Lists

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given k sorted linked lists, merge them all into one sorted linked list and return its head. Any of the lists may be empty, and k may be zero.

    The natural extension of Merge Two Sorted Lists, and a classic heap question. It's also how databases and log systems merge many sorted runs. Original problem: LeetCode 23.

    Example

    Three sorted lists of 1-4-5, 1-3-4 and 2-6 merge into one sorted list of eight nodes.
    Three sorted lists of 1-4-5, 1-3-4 and 2-6 merge into one sorted list of eight nodes.
    Input:  [1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6]
    Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
    Input:  []
    Output: null

    Constraints (assumed)

    • 0 ≤ k ≤ 10,000; total nodes N ≤ 10,000.
    • Each list sorted ascending.

    What this question tests

    • Generalizing a two-way merge to k ways efficiently.
    • Using a heap to always find the smallest of k candidates in O(log k).
    • Comparing with divide and conquer and explaining why one-by-one merging is slow.

    Questions to ask first

    1. Can lists be empty, and can k be 0? (Here: yes to both.)
    2. Can I reuse the nodes? (Here: yes.)
    3. Roughly how big are k and N? It decides whether the log k factor matters.
    4. Is the merge required to be stable for equal values? Usually not; tie-break by list index if so.