Start learning free

LESSON 325 OF 445 · LINKED LISTS

Merge K Sorted Lists in Rust: O(n × k) by Scanning the Heads

Practice O(n × 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] <= 107
  • 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 × k) time and use O(1) extra space apart from the merged list's new nodes (one per value), where n is the total number of nodes across all lists and k is the number of lists.
(A faster O(n log k) solution, with a min-heap, has its own lesson.)


Hints:

The output is sorted: at every moment you only need the smallest current head across all lists.
What's the simplest way to find it?

Use a dummy sentinel node and a tail walker.
Each iteration: scan all k heads, pick the smallest, append a new node with its value after tail, move tail onto it, and advance the chosen list. Repeat until every list is exhausted.

We produce n output nodes, and each one costs an O(k) scan of all heads — Time Complexity is O(n × k).
Apart from the merged list it returns (one new node per value), the solution keeps only the dummy node and a few variables, so the Extra Space is O(1).
STEP 1 OF 14
    Ctrl + Enter to check

    RUST · LINKED LISTS

    Merge K Sorted Lists in Rust, explained

    Problem overview

    The function merge_k_lists receives a vector of k linked lists, each sorted in ascending order. Each list is an Option<Box<ListNode>>: None for an empty list, or Some holding the first node. The function returns one sorted linked list containing every value from all of them. There can be no lists at all, or only empty ones, and then the answer is the empty list, None.

    For the lists 1->4->5, 1->3->4 and 2->6, the merged list is 1->1->2->3->4->4->5->6. The values are between -10,000 and 10,000,000, and the lists hold at most 10,000 nodes in total.

    The lesson's target is O(n × k) time, where n is the total number of nodes and k the number of lists. A faster O(n log k) version with a min-heap exists, and this lesson is the simpler scan.

    Approach: always take the smallest head

    Each input list is sorted, so its smallest unused value is its current first node, its head. The smallest value still waiting anywhere is therefore the smallest of the k heads. Take that one, append it to the output, advance that list to its next node, and repeat until every list is empty.

    Finding the smallest head is a plain loop over the k lists. It is O(k) per output node, and there are n output nodes, which gives O(n × k).

    To build the output without special-casing the first node, use a dummy node placed before the real head, plus a tail reference that points at the last node appended so far. Every append happens at tail.next. At the end, dummy.next is the head of the merged list.

    On the example, the heads are 1, 1 and 2. The scan picks the first 1, because ties go to the earlier list. That list's head becomes 4, so the heads are now 4, 1 and 2, the next pick is the second list's 1, and so on until the heads run out.

    Step by step

    1. Create the dummy. Box::new(ListNode::new(0)) is a node whose value is never used. Declare it mut, because its next will change.
    2. Create the walker tail as &mut dummy, a mutable reference to the dummy. It will move down the output as nodes are appended.
    3. Loop while any list has nodes. The condition calls a helper, any_non_null, that the lesson writes at the end.
    4. Start with no choice. ind is an i32 set to -1, meaning "no list picked yet". It is signed so that -1 can be stored, and it is cast to usize when used as an index.
    5. Scan all the lists with for i in 0..lists.len().
    6. Update the best choice. A list is a candidate when it is Some. It replaces the current choice when nothing has been picked yet, or when its head value is strictly smaller than the picked list's head. Strict comparison keeps the earlier list on ties.
    7. Append a new node with the chosen head's value, at tail.next.
    8. Advance the chosen list. take() removes the head node from the vector slot, leaving None. The code then moves on to that node's next and stores it back in the slot.
    9. Move tail onto the node just appended.
    10. Return dummy.next as the last expression of the function.
    11. Write the helper. any_non_null borrows the vector as a slice, loops over it, returns true at the first Some, and returns false after the loop.

    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 dummy = Box::new(ListNode::new(0));
        let mut tail = &mut dummy;
        while Self::any_non_null(&lists) {
            let mut ind: i32 = -1;
            for i in 0..lists.len() {
                if lists[i].is_some() && (ind == -1 || lists[i].as_ref().unwrap().val < lists[ind as usize].as_ref().unwrap().val) {
                    ind = i as i32;
                }
            }
            tail.next = Some(Box::new(ListNode::new(lists[ind as usize].as_ref().unwrap().val)));
            lists[ind as usize] = lists[ind as usize].take().unwrap().next;
            tail = tail.next.as_mut().unwrap();
        }
        dummy.next
    }

    fn any_non_null(lists: &[Option<Box<ListNode>>]) -> bool {
        for l in lists {
            if l.is_some() {
                return true;
            }
        }
        false
    }
}

    On the first example it produces [1, 1, 2, 3, 4, 4, 5, 6], on an empty vector of lists it produces an empty list, and on [None] it produces an empty list as well.

    The Rust details worth a closer look:

    • The list type. Option<Box<ListNode>> is Rust's way of writing a nullable pointer. None ends a list, and Box gives each node a fixed-size handle to its heap allocation, which a recursive struct needs.
    • mut lists. The vector is owned and modified: each step assigns a new head into one slot, so the parameter must be declared mut.
    • as_ref().unwrap(). It looks at a head without taking it. as_ref() turns &Option<Box<ListNode>> into Option<&Box<ListNode>>, and unwrap() gets the reference out. The is_some() check earlier in the same condition keeps the unwrap safe, since the && short-circuits.
    • take(). Writing lists[i].take() moves the value out and leaves None behind. That is how the code gets ownership of a node without breaking the vector. Without it, moving a node out of an indexed slot is a compile error.
    • The new nodes are copies of values. The merged list is built from fresh ListNode values, and the input nodes are dropped as they are consumed. The code doesn't re-link the old nodes.
    • The reference tail. &mut dummy borrows the dummy mutably, and tail = tail.next.as_mut().unwrap() re-points it to the node it just appended. dummy.next is returned only after the loop, when tail is no longer used.
    • Casting the index. ind as usize is safe here because ind is only read after the scan has set it to a valid position. With at least one non-empty list, the scan always does.

    Complexity

    Time: O(n × k). The outer loop runs once per output node, so n times. Each pass scans k lists to find the smallest head, and the helper's check costs up to k more. That is O(k) per node, giving O(n × k).

    Space: O(1) beyond the output. The merged list holds one new node per value and is the required result. Apart from it, the function keeps the dummy, the walker and a few integers.

    Edge cases and common mistakes

    • No lists. An empty vector never enters the loop, so dummy.next is None.
    • Only empty lists. [None] or [None, None] returns None for the same reason.
    • Some lists empty. [None, 3->5, None] gives [3, 5]. The is_some() test skips empty slots.
    • Equal heads. Lists 1->1 and 1 give [1, 1, 1]. No value is lost or merged, because equal values are each appended in turn.
    • Using <= instead of <. The result is still sorted, but the choice then goes to the later list on ties.
    • Reading a head before checking is_some(). Unwrapping a None panics. Keep the check ahead of the comparison in the same condition.
    • Forgetting to advance the list. If the chosen slot isn't replaced with its next, the same value is taken forever and the loop never ends.

    Testing

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