Merge k sorter lists

Linked List Divide and Conquer Heap (Priority Queue) Merge Sort

58.9% acceptance

Jan 12, 2026

21176

791

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

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

struct MinHeapNode(Option<Box<ListNode>>);

impl PartialEq for MinHeapNode {
  fn eq(&self, other: &Self) -> bool {
    self.0.as_ref().unwrap().val == other.0.as_ref().unwrap().val
  }
}

impl Eq for MinHeapNode {}

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

impl Ord for MinHeapNode {
  fn cmp(&self, other: &Self) -> Ordering {
    other.0.as_ref().unwrap().val.cmp(&self.0.as_ref().unwrap().val)
  }
}

impl Solution {
  pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
    let mut heap = BinaryHeap::new();
    
    // Push all non-empty list heads into the heap
    for list in lists {
      if list.is_some() {
        heap.push(MinHeapNode(list));
      }
    }
    
    let mut dummy = Box::new(ListNode::new(0));
    let mut current = &mut dummy;
    
    while let Some(MinHeapNode(mut node)) = heap.pop() {
      if let Some(mut n) = node.take() {
        // If this node has a next, push it to heap
        if n.next.is_some() {
          heap.push(MinHeapNode(n.next.take()));
        }
        
        // Append current smallest node to result
        current.next = Some(n);
        current = current.next.as_mut().unwrap();
      }
    }
    
    dummy.next
  }
}