impl Solution {
    unsafe fn merge2(
        lists: &mut Vec<Option<Box<ListNode>>>,
        s: usize,
        e: usize,
    ) -> Option<Box<ListNode>> {
        use std::mem::{forget, transmute, uninitialized};
        use std::ptr::write;

        if s == e {
            return lists[s].take();
        } else {
            let mid = (s + e) / 2;
            let mut lhs: *mut ListNode = transmute(Solution::merge2(lists, s, mid));
            let mut rhs: *mut ListNode = transmute(Solution::merge2(lists, mid + 1, e));
            let mut head = uninitialized();
            let mut tail: *mut ListNode = &mut head;

            unsafe fn transfer(dst: &mut *mut ListNode, src: &mut *mut ListNode) {
                write(&mut (**dst).next, transmute(*src));
                *dst = *src;
                *src = transmute((*src).read().next);
            }

            while !lhs.is_null() && !rhs.is_null() {
                if (*lhs).val <= (*rhs).val {
                    transfer(&mut tail, &mut lhs);
                } else {
                    transfer(&mut tail, &mut rhs);
                }
            }
            if !lhs.is_null() {
                write(&mut (*tail).next, transmute(lhs));
            } else {
                write(&mut (*tail).next, transmute(rhs));
            }
            let ans = (&head.next as *const Option<Box<ListNode>>).read();
            forget(head);
            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);
            unsafe { Solution::merge2(&mut lists, s, e) }
        }
    }
}