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)
                }
            }
        }
    }
}