如何从链接列表的末尾删除第N个节点? [英] How to remove the Nth node from the end of a linked list?

问题描述

这是我用来表示单个链表的数据结构:

This is the data structure I am using to represent a single linked list:

type Link = Option<Box<Node>>;

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

我想实现一种从列表末尾删除第N个节点的方法:

I would like to implement a method to remove the Nth node from the end of the list:

// 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

我一直都在和借阅检查器打架:

I am fighting with the borrow checker all the time:

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

如何实现方法的其余部分?

How can I implement the remaining part of the method?

请注意，我的方法不使用self作为参数，并且列表参数至少需要在当前实现中移动两次.

Please note my methods does not take self as argument and the list argument needs to be moved twice at least with the current implementation.

推荐答案

这是您无需使用递归即可编写方法的方法.

This is how you could write the method without using recursion.

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();
}

不幸的是，我没有通过使用更高效的运行器模式来使借阅检查器感到满意.

Unfortunately, I didn't manage to make the borrow checker happy by using the more efficient runner pattern.

这篇关于如何从链接列表的末尾删除第N个节点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！