LeetCode 21 - Merge Two Sorted Lists

LeetCode 21 - Merge Two Sorted Lists.md

LeetCode 21 - Merge Two Sorted Lists

Rust Implementation

ListNode struct

#[derive(Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

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

Final Version

impl Ord for ListNode {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.val.cmp(&self.val)
    }
}

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

pub fn merge_two_lists(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut result = None;
    let mut result_mut_ref = &mut result;
    let mut binary_heap: BinaryHeap<Option<Box<ListNode>>> = {
        match (list1.as_ref(), list2.as_ref()) {
            (Some(_), Some(_)) => BinaryHeap::from([list1, list2]),
            (Some(_), None) => BinaryHeap::from([list1]),
            (None, Some(_)) => BinaryHeap::from([list2]),
            (None, None) => BinaryHeap::from([]),
        }
    };
    while let Some(mut list_node) = binary_heap.pop() {
        let next = list_node
            .as_mut()
            .and_then(|list_node_mut| list_node_mut.next.take());
        if next.is_some() {
            binary_heap.push(next);
        }
        *result_mut_ref = list_node;
        result_mut_ref = &mut result_mut_ref.as_mut().unwrap().next;
    }
    result
}