CODEWITHSUNDEEP
listrust
Nick
Nick

Reputation: 10499

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,
}

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?

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.

Upvotes: 4

Views: 1324

Answers (1)

gliderkite
gliderkite

Reputation: 8928

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.

Upvotes: 2

Related Questions