Mastering the Merge K Sorted Lists Problem in Rust 🦀

Solving LeetCode problems in Rust often feels like a different game. While the logic remains the same, Rust’s strict ownership rules and the Option<Box<ListNode>> structure turn a Hard problem into a masterclass in memory management.

Today, we’re breaking down the Merge K Sorted Lists problem. We'll explore why a Brute Force approach is tempting but slow, and how to implement the optimal solution using a Min-Heap.

The Challenge

We are given an array of linked lists, each sorted in ascending order. Our goal is to merge them into one single, sorted linked list.

link to problem : https://leetcode.com/problems/merge-k-sorted-lists/

complexity : Hard

1. The Quick and Dirty Approach: Vector Sorting

The most intuitive way is to extract all values into a Vec, sort them, and rebuild the list.

pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
    let mut vals = Vec::new();
    for mut list in lists {
        while let Some(node) = list {
            vals.push(node.val);
            list = node.next;
        }
    }
    vals.sort();

    let mut head = None;
    for &val in vals.iter().rev() {
        let mut new_node = Box::new(ListNode::new(val));
        new_node.next = head;
        head = Some(new_node);
    }
    head
}

The Verdict: *Time Complexity: is the total number of nodes , O(n).

• Space Complexity: because we store every value in a vector.
• Is it good? It works, but it’s not memory-efficient for large datasets.

---

2. The Optimal Approach: Using a Binary Heap (Min-Heap)

Instead of sorting everything at once, we only need to compare the heads of each list. By putting the heads of all lists into a Min-Heap, we can always extract the smallest element in time.

The Problem: Rust's BinaryHeap is a Max-Heap

By default, std::collections::BinaryHeap returns the largest element. To get a Min-Heap, we create a small wrapper and reverse the comparison logic.

use std::collections::BinaryHeap;
use std::cmp::Ordering;

#[derive(Eq, PartialEq)]
struct NodeWrapper(Box<ListNode>);

impl Ord for NodeWrapper {
    fn cmp(&self, other: &Self) -> Ordering {
        // We swap 'other' and 'self' to create a Min-Heap
        other.0.val.cmp(&self.0.val)
    }
}

impl PartialOrd for NodeWrapper {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

The Implementation

With our wrapper ready, the logic becomes:

1. Push the first node of every list into the heap.
2. Pop the smallest node and attach it to our result.
3. If that popped node had a next node, push that into the heap.

impl Solution {
    pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        let mut heap = BinaryHeap::new();

        for head in lists {
            if let Some(node) = head {
                heap.push(NodeWrapper(node));
            }
        }

        let mut dummy = Box::new(ListNode::new(0));
        let mut curr = &mut dummy;

        while let Some(NodeWrapper(mut smallest_node)) = heap.pop() {
            if let Some(next_node) = smallest_node.next.take() {
                heap.push(NodeWrapper(next_node));
            }
            curr.next = Some(smallest_node);
            curr = curr.next.as_mut().unwrap();
        }

        dummy.next
    }
}

Summary

The Min-Heap approach is the gold standard for this problem. It respects the fact that the input lists are already sorted, meaning we only ever need to track elements at a time.

What's your favorite way to handle Linked Lists in Rust? Let me know in the comments!