impl Solution {
    pub fn merge_k_lists(mut lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        let mut head = None;
        for mut list in lists {
            head = Solution::merge_two_lists(head, list);
        }
        return head;
    }

    pub fn merge_two_lists(mut l1: Option<Box<ListNode>>, mut l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = ListNode::new(0);
        let mut cur = &mut dummy;
        while l1.is_some() && l2.is_some() {
            let v1 = if let Some(ref node) = l1 { node.val } else { i32::MIN };
            let v2 = if let Some(ref node) = l2 { node.val } else { i32::MIN };
            let v = min(v1, v2);
            let new_node = ListNode::new(v);
            cur.next = Some(Box::new(new_node));
            cur = cur.next.as_mut().unwrap();
            if v1 < v2 {
                if let Some(ref node) = l1 { l1 = l1.unwrap().next; }
            } else {
                if let Some(ref node) = l2 { l2 = l2.unwrap().next; }
            }
        }
        if l1.is_some() {
            cur.next = l1;
        }
        if l2.is_some() {
            cur.next = l2;
        }
        return dummy.next;
    }
}

impl Solution {
    pub fn merge_k_lists(mut lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        let mut head = None;
        for mut list in lists {
            head = Solution::merge_two_lists(head, list);
        }
        return head;
    }

    fn merge_two_lists(mut l1: Option<Box<ListNode>>, mut l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = ListNode::new(0);
        let mut cur = &mut dummy;
        while l1.is_some() && l2.is_some() {
            match (&l1, &l2) {
                (Some(v1), Some(v2)) => {
                    if v1.val < v2.val {
                        l1 = Solution::collect_node(l1, &mut cur)
                    } else {
                        l2 = Solution::collect_node(l2, &mut cur);
                    }
                }
                _ => {}
            }
            cur = cur.next.as_mut().unwrap();
        }
        cur.next = if l1.is_some() { l1 } else { l2 };
        return dummy.next;
    }

    #[inline]
    fn collect_node(mut list: Option<Box<ListNode>>, mut cur: &mut &mut ListNode) -> Option<Box<ListNode>> {
        if let Some(mut node) = list {
            let next = node.next.take();
            cur.next = Some(node);
            next
        } else {
            None
        }
    }
}

impl Solution {
    pub fn merge_k_lists(mut lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        let len = lists.len();
        if len == 0 {
            return None;
        }
        Solution::merge(&mut lists, 0, len - 1)
    }

    fn merge(lists: &mut Vec<Option<Box<ListNode>>>, l: usize, r: usize) -> Option<Box<ListNode>> {
        if l == r {
            return lists[l].clone();
        }
        if l > r {
            return None;
        }
        let mid = l + (r - l) / 2;
        let a = Solution::merge(lists, l, mid);
        let b = Solution::merge(lists, mid + 1, r);
        Solution::merge_two_lists(a, b)
    }


    fn merge_two_lists(mut l1: Option<Box<ListNode>>, mut l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = ListNode::new(0);
        let mut cur = &mut dummy;
        while l1.is_some() && l2.is_some() {
            match (&l1, &l2) {
                (Some(v1), Some(v2)) => {
                    if v1.val < v2.val {
                        l1 = Solution::collect_node(l1, &mut cur)
                    } else {
                        l2 = Solution::collect_node(l2, &mut cur);
                    }
                }
                _ => {}
            }
            cur = cur.next.as_mut().unwrap();
        }
        cur.next = if l1.is_some() { l1 } else { l2 };
        return dummy.next;
    }

    #[inline]
    fn collect_node(mut list: Option<Box<ListNode>>, mut cur: &mut &mut ListNode) -> Option<Box<ListNode>> {
        if let Some(mut node) = list {
            let next = node.next.take();
            cur.next = Some(node);
            next
        } else {
            None
        }
    }
}