Как удалить N-й узел из конца связанного списка?

Question

Это структура данных, которую я использую для представления единого связанного списка:

type Link = Option<Box<Node>>;

pub struct Node {
    elem: i32,
    next: Link,
}

Я хотел бы реализовать метод удаления N-го узла из конца списка:

// Original list
A -> B -> C -> D -> None

// remove 1 from the end of the original list
A -> B -> C -> None

// Remove 2 from the end of the original list
A -> B -> D -> None

Я все время бьюсь с контролером заимствований:

fn remove_nth_node_from_end(list: &mut Link, n: usize) {
    if list.is_none() {
        return;
    }
    let mut i = 0;
    let mut fast = list;
    while let Some(ref mut node) = {fast} {
        if i == n {
            break;
        }
        i += 1;
        fast = &mut node.next;
    }

    // issues start here, since I need to mutably borrow
    // the list (and it has already been moved above for fast)
    // but without moving I have troubles implementing the above loop
    let mut slow = &mut list;
    // iterate over the list using slow and fast
    // when fast is None
    //   slow.next = slow.next.next
}

error[E0596]: cannot borrow immutable argument `list` as mutable
  --> src/lib.rs:25:25
   |
25 |     let mut slow = &mut list;
   |                         ^^^^ cannot borrow mutably
help: consider removing the `&mut`, as it is an immutable binding to a mutable reference
   |
25 |     let mut slow = list;
   |                    ^^^^

error[E0382]: use of moved value: `list`
  --> src/lib.rs:25:25
   |
13 |     let mut fast = list;
   |         -------- value moved here
...
25 |     let mut slow = &mut list;
   |                         ^^^^ value used here after move
   |
   = note: move occurs because `list` has type `&mut std::option::Option<std::boxed::Box<Node>>`, which does not implement the `Copy` trait

Как я могу реализовать оставшуюся часть метода?

Обратите внимание, что мои методы не принимают self в качестве аргумента, а аргумент списка необходимо переместить как минимум дважды в текущей реализации.

Answer 1

Вот как вы могли бы написать метод без использования рекурсии.

fn remove_nth(list: &mut Link, n: usize) {
    if list.is_none() {
        return;
    }
    let get_length = |l: &Link| {
        let mut length = 0;
        let mut current = l;
        while let Some(n) = {current} {
            length += 1;
            current = &n.next;
        }
        length
    };
    let length = get_length(list);
    let mut i = 0;
    let mut current = list;
    while i < length - n {
        if let Some(link) = {current} {
            current = &mut link.next;
        } else {
            panic!("Invalid node!");
        }
        i += 1;
    }
    *current = current.as_mut().unwrap().next.take();
}

К сожалению, мне не удалось порадовать контролера заимствований, используя более эффективный шаблон бегуна.