# Merge k Sorted Lists in Rust

impl Solution {
// Function to merge k sorted lists
pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
// If the list is empty, return None
if lists.is_empty() {
return None;
}
// Call the divide and conquer function on the list
Solution::divide_and_conquer(&lists, 0, lists.len() - 1)
}

// Function to divide the problem into smaller parts and then merge the results
fn divide_and_conquer(
lists: &Vec<Option<Box<ListNode>>>,
start: usize,
end: usize,
) -> Option<Box<ListNode>> {
// If the start index is equal to the end index, return the list at that index
if start == end {
return lists[start].clone();
}
// Calculate the mid index
let mid = start + (end - start) / 2;
// Recursively call divide and conquer on the first half of the list
let l1 = Solution::divide_and_conquer(lists, start, mid);
// Recursively call divide and conquer on the second half of the list
let l2 = Solution::divide_and_conquer(lists, mid + 1, end);
// Merge the two halves and return the result
Solution::merge_two_lists(l1, l2)
}

// Function to merge two sorted lists
fn merge_two_lists(
l1: Option<Box<ListNode>>,
l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
// Match on the two lists
match (l1, l2) {
// If both lists are None, return None
(None, None) => None,
// If one of the lists is None, return the other list
(None, Some(node)) | (Some(node), None) => Some(node),
// If both lists are Some, merge them
(Some(node1), Some(node2)) => {
// If the value of the first node is less than the value of the second node
if node1.val < node2.val {
let mut node1 = node1;
// Set the next of the first node to the result of merging the rest of the first list with the second list
node1.next = Solution::merge_two_lists(node1.next, Some(node2));
// Return the first node
Some(node1)
} else {
let mut node2 = node2;
// Set the next of the second node to the result of merging the first list with the rest of the second list
node2.next = Solution::merge_two_lists(Some(node1), node2.next);
// Return the second node
Some(node2)
}
}
}
}
}