Как преобразовать связанный список Option <Box <ListNode>> в Vec <i32>?

Question

Я хочу преобразовать следующий тип Option<Box<ListNode>> в тип Vec<i32>:

fn main() {
    Some(ListNode {
        val: 3,
        next: Some(ListNode {
            val: 4,
            next: Some(ListNode { val: 2, next: None }),
        }),
    })
}

Я хочу реализовать функцию list_to_vec:

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    pub fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }

    pub fn vec_to_list(mut value: Vec<i32>) -> Option<Box<ListNode>> {
        match value.pop() {
            Some(x) => Some(Box::new(ListNode {
                val: x,
                next: ListNode::vec_to_list(value),
            })),
            None => None,
        }
    }
    pub fn list_to_vec(mut value: &Option<ListNode>) -> Vec<i32> {
        //????????????????????????????
    }
}

Требуемый вывод

[3, 4, 2]

---

Я пробовал:

pub fn list_to_vec(mut value: &Option<ListNode>) -> Vec<i32> {
    let mut v = vec![];
    match value {
        Some(x) => {
            &v.push(x.val);
            Self::list_to_vec(x.next)
        }
        None => v,
    }
}

let h = ListNode::vec_to_list(vec![2, 4, 3]);
println!("{:#?}", ListNode::list_to_vec(&h));

ошибка:

error[E0308]: mismatched types
  --> src\main.rs:27:56
   |
27 |           Some(x) => {&v.push(x.val);Self::list_to_vec(x.next)},
   |                                                        ^^^^^^ expected reference, found enum `std::option::Option`
   |
   = note: expected type `&std::option::Option<ListNode>`
              found type `std::option::Option<std::boxed::Box<ListNode>>`

error[E0308]: mismatched types
  --> src\main.rs:74:40
   |
74 | println!("{:#?}",ListNode::list_to_vec(&h));
   |                                        ^^ expected struct `ListNode`, found struct `std::boxed::Box`
   |
   = note: expected type `&std::option::Option<ListNode>`
              found type `&std::option::Option<std::boxed::Box<ListNode>>`

Answer 1

Рекурсивное решение здесь не требуется и, вероятно, не будет таким же эффективным, как итеративное решение.

Принятие права собственности:

pub fn list_to_vec(mut value: Option<Box<ListNode>>) -> Vec<i32> {
    let mut v = Vec::new();
    while let Some(n) = value {
        v.push(n.val);
        value = n.next;
    }
    v
}

По ссылке:

pub fn list_to_vec(mut value: &Option<Box<ListNode>>) -> Vec<i32> {
    let mut v = Vec::new();
    while let Some(n) = value {
        v.push(n.val);
        value = &n.next;
    }
    v
}

Answer 2

Вы взорвете свой стек, если вы не выполните хвостовую рекурсивную функцию, ваш vec_to_list() не может обработать вектор среднего размера. Для вашего list_to_vec() вы можете просто внедрить Iterator и собрать его, быстрый и грязный пример:

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

pub struct ListIter<'a> {
    iter: &'a Option<Box<ListNode>>,
}

impl<'a> Iterator for ListIter<'a> {
    type Item = i32;
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(cur) = self.iter {
            self.iter = &cur.next;
            Some(cur.val)
        } else {
            None
        }
    }
}

impl ListNode {
    pub fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }

    pub fn vec_to_list<'a>(
        value: impl IntoIterator<IntoIter = impl DoubleEndedIterator<Item = &'a i32>, Item = &'a i32>,
    ) -> Option<Box<ListNode>> {
        Self::vec_to_list_aux(value.into_iter().rev().copied(), None)
    }

    fn vec_to_list_aux(
        value: impl Iterator<Item = i32>,
        accu: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut value = value;
        match value.next() {
            Some(x) => {
                Self::vec_to_list_aux(value, Some(Box::new(ListNode { val: x, next: accu })))
            }
            None => accu,
        }
    }

    pub fn list_to_vec(list: &Option<Box<ListNode>>) -> Vec<i32> {
        Self::iter(list).collect()
    }

    fn iter(list: &Option<Box<ListNode>>) -> ListIter {
        ListIter { iter: &list }
    }
}

fn main() {
    let list = ListNode::vec_to_list(&[3, 4, 2]);

    println!("{:#?}", list);
    println!("{:?}", ListNode::list_to_vec(&list));
}

Answer 3

Я решил это.

pub fn list_to_vec(mut value: Option<Box<ListNode>>, mut v_cup: Vec<i32>) -> Vec<i32> {
    match value {
        Some(x) => {
            v_cup.push(x.val);
            Self::list_to_vec(x.next, v_cup)
        }
        None => v_cup,
    }
}

let h = ListNode::vec_to_list(vec![2, 4, 3]);
let v_cup = vec![];
println!("{:?}", ListNode::list_to_vec(h, v_cup));