Start learning free

LESSON 311 OF 414 · LINKED LISTS

Merge K Sorted Lists in Rust: Min-Heap, O(n log k) Time

Practice O(N log k) Read the full explanation

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.
Note:

Your algorithm should run in O(n log k) time and use O(k) extra space, where n is the total number of nodes across all lists and k is the number of lists.


Hints:

The brute force re-scans every list head each time. What data structure gives you the smallest of k values in O(log k) instead of O(k)?

Use a min-heap seeded with the head of every non-empty list, ordered by the node's value.
Each iteration: extract the smallest node, append a copy of its value to the merged tail, and if it has a successor, push that successor onto the heap.
When the heap is empty, every list has been fully consumed.

The heap holds at most k nodes at any time. Each of the n output nodes costs one extract and at most one insert, each O(log k) — Time Complexity is O(n log k).
The heap itself uses O(k) extra space.

STEP 1 OF 11
    Ctrl + Enter to check

    RUST · LINKED LISTS

    Merge K Sorted Lists in Rust, explained

    Problem overview

    The function merge_k_lists receives a vector lists of k linked lists, each sorted in ascending order, and returns one sorted list that holds all their values. A list is an Option<Box<ListNode>>, so an empty list is None.

    For [[1, 4, 5], [1, 3, 4], [2, 6]] the answer is [1, 1, 2, 3, 4, 4, 5, 6]. An empty vector of lists gives an empty list, and so does a vector holding a single empty list. Values range from -10,000 to 10,000, there are at most 10,000 nodes in total, and the statement asks for O(n log k) time and O(k) extra space, where n is the total number of nodes.

    Approach: always take the smallest front value

    Each list is sorted, so the overall minimum is always the front of one of the lists. The simplest method scans all k fronts for the smallest one, appends it and repeats. That costs O(k) per output node and O(n * k) in total.

    A min-heap does the same job faster. It holds at most one entry per list, the current front of that list. Removing the smallest entry and adding the next front from the same list each take O(log k). For each of the n output nodes the loop does one removal and at most one insertion, so the time is O(n log k). The heap never holds more than k entries, so its space is O(k).

    On the example, the heap starts with the fronts 1, 1 and 2. The smallest 1 comes out, and the next value from its list, 4, goes in. The smallest is now the other 1, and its list contributes 3. This continues until every list is used up and the heap is empty.

    Step by step

    1. Create the heap. BinaryHeap in Rust is a max-heap: pop returns the largest item. Wrapping each entry in std::cmp::Reverse flips the comparison, so the smallest entry comes out first. The entries are (val, idx) pairs: a node's value and the index of the list it came from. Both types are written with their full paths because neither is imported.
    2. Visit every list with for (i, head) in lists.iter().enumerate(), which pairs each head with its index.
    3. Seed the heap. If head is Some(node), push Reverse((node.val, i)). Empty lists add nothing.
    4. Create a dummy node, Box::new(ListNode::new(0)). The merged list will be dummy.next.
    5. Create the tail walker, let mut tail = &mut dummy;, a mutable reference that always points at the last node appended.
    6. Loop with while let Some(Reverse((val, idx))) = min_nodes.pop(). The pattern tests for an empty heap and takes the pair apart in one step.
    7. Append a new node holding val as tail.next.
    8. Advance the source list. lists[idx].take().unwrap() removes the front node from that slot, and lists[idx] = node.next puts the rest of the list back. The slot now holds the next candidate from that list.
    9. Refill the heap. If lists[idx] is still Some, push its new front with the same idx.
    10. Move the tail walker with tail = tail.next.as_mut().unwrap().
    11. Return dummy.next as the last expression.

    The solution in Rust

    struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

impl Solution {
    fn merge_k_lists(mut lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        let mut min_nodes: std::collections::BinaryHeap<std::cmp::Reverse<(i32, usize)>> = std::collections::BinaryHeap::new();
        for (i, head) in lists.iter().enumerate() {
            if let Some(node) = head {
                min_nodes.push(std::cmp::Reverse((node.val, i)));
            }
        }
        let mut dummy = Box::new(ListNode::new(0));
        let mut tail = &mut dummy;
        while let Some(std::cmp::Reverse((val, idx))) = min_nodes.pop() {
            tail.next = Some(Box::new(ListNode::new(val)));
            let node = lists[idx].take().unwrap();
            lists[idx] = node.next;
            if let Some(next_node) = &lists[idx] {
                min_nodes.push(std::cmp::Reverse((next_node.val, idx)));
            }
            tail = tail.next.as_mut().unwrap();
        }
        dummy.next
    }
}

    Rust details worth knowing:

    • Why the heap stores indices. The heap could hold the nodes themselves, but each node is owned by its list inside lists, and the code needs to keep changing those lists while the heap exists. Storing (val, idx) keeps the heap free of borrows. When an entry comes out, idx says which slot to take the node from.
    • Tuples compare field by field, so the heap orders by value first. When values tie, the smaller list index wins. With the entries (4, 0), (1, 2), (1, 1) and (5, 0) in a Reverse heap, they come out as (1, 1), (1, 2), (4, 0), (5, 0). A plain BinaryHeap holding 4, 1 and 5 returns Some(5) from pop, which is why Reverse is needed.
    • The merged list is built from new nodes. The code allocates a fresh Box for each output value and discards the old nodes as it consumes them: take() moves the old node out, and it is dropped at the end of the loop pass after its next has been moved into the slot. The output is a separate list, not a relinking of the inputs.
    • mut lists. The parameter is declared mut so the function may call take() on its elements and assign to them.
    • Borrows are short. The first loop borrows lists only to read the heads and is finished before the main loop modifies it. In the main loop, if let Some(next_node) = &lists[idx] borrows only for the push.
    • The tail cursor. A &mut to the last node lets each new node be attached in constant time. The final line of the loop moves the cursor onto the node that was just added.

    Complexity

    Time: O(n log k). Seeding the heap costs at most k pushes of O(log k) each. The main loop runs n times with one pop and at most one push, each O(log k).

    Space: O(k) extra. The heap holds at most one entry per list. The output list itself has n nodes, but it is the answer, not scratch space. The input nodes are freed as they are consumed.

    Edge cases and common mistakes

    • No lists. lists = [] gives an empty heap, the loop never runs, and the function returns None.
    • Only empty lists. [None] also leaves the heap empty and returns None.
    • Some lists empty. [None, [-1, 5], None] gives [-1, 5]. Empty lists are skipped when the heap is seeded.
    • Negative values. They order correctly in an i32 tuple. No offset is needed.
    • Forgetting Reverse. The heap would hand back the largest front each time, so the merged list would not be sorted.
    • Forgetting to refill the heap. If the next front from the same list isn't pushed, each list contributes only its first value.
    • Advancing tail before the append. The walker must be on the last node when tail.next is assigned.

    Testing

    • [[1, 4, 5], [1, 3, 4], [2, 6]] gives [1, 1, 2, 3, 4, 4, 5, 6].
    • [] gives [].
    • [[]] gives [].
    • [[], [-1, 5], []] gives [-1, 5].
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free