Problem statement

You are given an array lists of k linked lists, each sorted in ascending order. Merge all of them into a single sorted linked list and return its head.

Example 1

Input: lists = [[1,4,9],[2,3,8],[5,6]]
Output: [1,2,3,4,5,6,8,9]
Explanation: The three sorted lists interleave into one sorted list of eight nodes.

Example 2

Input: lists = []
Output: []
Explanation: There are no lists at all, so the result is empty.

Example 3

Input: lists = [[],[7],[]]
Output: [7]
Explanation: Empty lists contribute nothing.

Constraints

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order
• The sum of lists[i].length does not exceed 10^4

Hints for Merge k Sorted Lists

1. Hint 1

   Merging two sorted lists is a standard linear-time step. How can you build a k-way merge out of it?

2. Hint 2

   Merging the lists one after another into a growing result costs O(k * N) in the worst case — the early nodes get copied over and over.

3. Hint 3

   Merge in rounds: pair list 0 with 1, 2 with 3, … then merge the results in pairs again. Every node takes part in only log k merges. (A min-heap of the k current heads works too.)

How to solve Merge k Sorted Lists

Divide and conquer: merging lists pairwise in rounds halves the number of lists each round, so after ⌈log2 k⌉ rounds one list remains, and each node is touched once per round.

Approach

1. If lists is empty, return an empty list.
2. With step = 1, merge lists[i] and lists[i + step] into lists[i] for i = 0, 2·step, 4·step, … while i + step < k.
3. Double step and repeat while step < k.
4. Return lists[0].
5. Merging two lists: keep a dummy head and a tail; repeatedly attach the smaller of the two current heads, then attach whatever remains.

Why it works

Each round merges disjoint pairs, so after the round with step s every lists[i] with i a multiple of 2s holds the merge of lists i … i + 2s - 1. When step reaches k, lists[0] holds all of them, in order because each two-list merge preserves sortedness.

Complexity

• Time — O(N log k) — N nodes in total
• Space — O(1) (the merges relink existing nodes)

Pitfalls

• Empty lists (null heads) inside lists, and lists itself empty, are both allowed.
• Merging sequentially into one accumulator is correct but quadratic in k on adversarial inputs.
• A heap-based merge must not compare node objects directly in languages that cannot order them — store (value, index) pairs.

Reference solution

Python

from typing import List, Optional

def merge_two(a, b):
    dummy = tail = ListNode(0)
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a if a else b
    return dummy.next

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    if not lists:
        return None
    k, step = len(lists), 1
    while step < k:
        for i in range(0, k - step, 2 * step):
            lists[i] = merge_two(lists[i], lists[i + step])
        step *= 2
    return lists[0]

Java

static ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a != null ? a : b;
    return dummy.next;
}

public static ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    for (int step = 1; step < lists.length; step *= 2)
        for (int i = 0; i + step < lists.length; i += 2 * step) lists[i] = mergeTwo(lists[i], lists[i + step]);
    return lists[0];
}

C++

ListNode* mergeTwo(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;
    int k = lists.size();
    for (int step = 1; step < k; step *= 2)
        for (int i = 0; i + step < k; i += 2 * step) lists[i] = mergeTwo(lists[i], lists[i + step]);
    return lists[0];
}

JavaScript

var mergeTwo = function(a, b) {
    var dummy = new ListNode(0), tail = dummy;
    while (a !== null && b !== null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a !== null ? a : b;
    return dummy.next;
};

var mergeKLists = function(lists) {
    if (lists.length === 0) return null;
    for (var step = 1; step < lists.length; step *= 2)
        for (var i = 0; i + step < lists.length; i += 2 * step) lists[i] = mergeTwo(lists[i], lists[i + step]);
    return lists[0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More heap problems

• The Skyline Problem Hard
• Longest Increasing Subsequence II Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Create Sorted Array Through Instructions Hard
• Reverse Pairs Hard
• Special Binary String Hard