impl Solution {
    pub fn merge2(
        lists: &mut Vec<Option<Box<ListNode>>>,
        s: usize,
        e: usize,
    ) -> Option<Box<ListNode>> {
        fn move_head(src: &mut Option<Box<ListNode>>, dst: &mut Option<Box<ListNode>>) {
            if let Some(mut node) = src.take() {
                *src = node.next.take();
                node.next = dst.take();
                *dst = Some(node);
            }
        }

        if s == e {
            return lists[s].take();
        } else {
            let mid = (s + e) / 2;
            let mut lhs = Solution::merge2(lists, s, mid);
            let mut rhs = Solution::merge2(lists, mid + 1, e);
            let mut head = None;
            while lhs.is_some() && rhs.is_some() {
                let lhs_head = lhs.as_ref().unwrap();
                let rhs_head = rhs.as_ref().unwrap();
                if lhs_head.val <= rhs_head.val {
                    move_head(&mut lhs, &mut head);
                } else {
                    move_head(&mut rhs, &mut head);
                }
            }
            while lhs.is_some() {
                move_head(&mut lhs, &mut head);
            }
            while rhs.is_some() {
                move_head(&mut rhs, &mut head);
            }
            let mut ans = None;
            while head.is_some() {
                move_head(&mut head, &mut ans);
            }
            ans
        }
    }

    pub fn merge_k_lists(mut lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        if lists.is_empty() {
            None
        } else {
            let (s, e) = (0, lists.len() - 1);
            Solution::merge2(&mut lists, s, e)
        }
    }
}