Как изменить связанный список, используя только указатели

Первое сообщение об ошибке, которое вы получаете, следующее (в Rust 1.80):

error[E0594]: cannot assign to data in an index of `Vec<&Box<ListNode>>`
  --> src/main.rs:51:9
   |
51 |         vec_ref[i].next = Some(*vec_ref[i + 1]);
   |         ^^^^^^^^^^^^^^^ cannot assign
   |
   = help: trait `IndexMut` is required to modify indexed content, but it is not implemented for `Vec<&Box<ListNode>>`

Сообщение об ошибке здесь немного неясно, но по сути оно возникает, потому что вы пытаетесь изменить элемент в Vec, однако элементы находятся за ссылкой &, поэтому они не изменяемы. Вам нужно изменить тип с Vec<&Box<ListNode>> на Vec<&mut Box<ListNode>>.

Однако это приводит к ряду других проблем в будущем, вызванных тем, что вы будете хранить несколько изменяемых ссылок на одни и те же объекты, что недопустимо в безопасном Rust. Вы можете обойти это, используя небезопасный Rust и изменяемые указатели вместо изменяемых ссылок, но в вашем конкретном случае я думаю, что есть лучшая альтернатива.

Если вы намерены удалить дубликаты, которые появляются рядом друг с другом, я думаю, ваш код можно значительно упростить. В частности, вам не нужны дополнительные Vec для отслеживания дедуплицированных узлов: вы можете просто изменить связанный список на месте, вот так:

pub fn delete_duplicates(head: &mut Option<Box<ListNode>>) {
    // Make sure that `node` is `Option<&mut Box<ListNode>>`, to
    // avoid taking ownership of nodes after the head (which would
    // not be allowed by Rust)
    let mut node = head.as_mut();

    while let Some(this) = node {
        // Loop through every node that shares the same value as `this`
        loop {
            if let Some(ref mut next) = this.next {
                if this.val == next.val {
                    // `this` and `next` have the same value.
                    // Connect `this` to `next.next`, so that the
                    // list changes from:
                    //
                    //   ... -> this -> next -> next.next -> ...
                    //
                    // to:
                    //
                    //   ... -> this -> next.next -> ...
                    //
                    // The use of `take()` ensures that `next.next`
                    // is replaced with `None` (this avoids taking
                    // multiple ownerships).
                    this.next = next.next.take();
                    continue;
                }
            }
            // Either there's no next node, or the next node has a
            // different value than `this`
            break;
        }
        node = this.next.as_mut();
    }
}

Ссылка на игровую площадку

Вот моя мысль: во-первых, вообще избегайте использования связанного списка в Rust, Rust просто не лучший язык для использования связанного списка из-за модели владения.

во-вторых, если вам нужен список ссылок, я думаю, вам следует постараться не слишком сильно возиться со ссылками. Об указателе уже трудно думать, не говоря уже о том, чтобы указатель соответствовал правилу владения.

подумайте о том, кому принадлежит часть данных.

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

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

    /// Functions I added for testing
    /// 
    /// Push an element to the end of the list
    pub fn push(&mut self, val: i32) {
        let mut current: &mut ListNode = self;
        while current.next.is_some() {
            current = current.next.as_mut().unwrap();
        }
        current.next = Some(Box::new(ListNode { val, next: None }));
    }
    /// Print Out the list
    pub fn print(&self) {
        print!("[{:>3?}]", self.val);
        let mut current: &ListNode = self;
        while current.next.is_some() {
            current = current.next.as_ref().unwrap();
            print!(" -> [{:>3?}]", current.val);
        }

        println!("");
    }
}

/// I refactored the whole function
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    // The head of the list, if there aren't a list, return None
    let mut head: Box<ListNode> = head?;
    let mut current: Option<Box<ListNode>> = head.next.take();
    let mut tail: &mut Box<ListNode> = &mut head;

    // we TAKE the second element as the current node
    //
    // you can think of it as
    //
    //               |- tail
    //               v
    // head : () -> [first val]
    //
    // current: () -> [second val] -> [thrid val] -> ...
    //

    // Then we keep dequeuing the current
    // when current is None, we know the list ended
    while let Some(mut c) = current {
        //
        //                                     | tail
        //                                     v
        //  head : () -> [1] -> [2] -> ... -> [4]
        //  c    : () -> [5] -> [6]-> ...
        //
        // TAKE out the next node as the next current
        current = c.next.take();
        //
        //                                        | tail
        //                                        v
        //  head    : () -> [1] -> [2] -> ... -> [4]
        //  c       : () -> [5]
        //  current : () -> [6] -> [7]-> ...
        //
        // if the c.val is not equal to the last list, we push it to the end of the list
        if c.val != tail.val {
            tail.next = Some(c);
            tail = tail.next.as_mut().unwrap();
            //
            //                                               | tail
            //                                               v
            //  head    : () -> [1] -> [2] -> ... -> [4] -> [5]
        }
    }

    Some(head)
}
fn main() {
    let mut list: ListNode = ListNode::new(1);
    list.push(2);
    list.push(2);
    list.push(3);
    list.push(4);
    list.print();
    let new_list: Box<ListNode> = delete_duplicates(Some(Box::new(list))).unwrap();
    new_list.print();
}

выход

[  1] -> [  2] -> [  2] -> [  3] -> [  4]
[  1] -> [  2] -> [  3] -> [  4]

таким образом, head владейте всем списком и tail управляйте его мутациями. которые соответствуют правилу владения, одному владельцу и только одной изменяемой ссылке.

Производительность

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

use std::io::Write;

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

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

    /// Functions I added for testing
    ///
    /// Push an element to the end of the list
    pub fn push(&mut self, val: i32) {
        let mut current: &mut ListNode = self;
        while current.next.is_some() {
            current = current.next.as_mut().unwrap();
        }
        current.next = Some(Box::new(ListNode { val, next: None }));
    }
    /// Print Out the list
    pub fn print(&self) {
        print!("[{:>3?}]", self.val);
        let mut current: &ListNode = self;
        while current.next.is_some() {
            current = current.next.as_ref().unwrap();
            print!(" -> [{:>3?}]", current.val);
        }

        println!("");
    }
}

/// I refactored the whole function
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    // The head of the list, if there aren't a list, return None
    let mut head: Box<ListNode> = head?;
    let mut current: Option<Box<ListNode>> = head.next.take();
    let mut tail: &mut Box<ListNode> = &mut head;

    // we TAKE the second element as the current node
    //
    // you can think of it as
    //
    //               |- tail
    //               v
    // head : () -> [first val]
    //
    // current: () -> [second val] -> [thrid val] -> ...
    //

    // Then we keep dequeuing the current
    // when current is None, we know the list ended
    while let Some(mut c) = current {
        //
        //                                     | tail
        //                                     v
        //  head : () -> [1] -> [2] -> ... -> [4]
        //  c    : () -> [5] -> [6]-> ...
        //
        // TAKE out the next node as the next current
        current = c.next.take();
        //
        //                                        | tail
        //                                        v
        //  head    : () -> [1] -> [2] -> ... -> [4]
        //  c       : () -> [5]
        //  current : () -> [6] -> [7]-> ...
        //
        // if the c.val is not equal to the last list, we push it to the end of the list
        if c.val != tail.val {
            tail.next = Some(c);
            tail = tail.next.as_mut().unwrap();
            //
            //                                               | tail
            //                                               v
            //  head    : () -> [1] -> [2] -> ... -> [4] -> [5]
        }
    }

    Some(head)
}

pub fn delete_duplicates_2(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    // take ownership of the head, and we will manipulate this directly.
    let mut current = head;
    // Mutable reference to 'current' node. We use 'as_mut' and 'and_then' to traverse and modify the list in place
    let mut current_ref = current.as_mut();

    while let Some(curr_node) = current_ref {
        // check if the next node is a duplicate
        while curr_node
            .next
            .as_ref()
            .map_or(false, |next_node| next_node.val == curr_node.val)
        {
            //skip the duplicate
            curr_node.next = curr_node.next.as_mut().unwrap().next.take();
        }
        // Move to the next node
        current_ref = curr_node.next.as_mut();
    }
    current
}

pub fn delete_duplicates_3(head: &mut Option<Box<ListNode>>) {
    // Make sure that `node` is `Option<&mut Box<ListNode>>`, to
    // avoid taking ownership of nodes after the head (which would
    // not be allowed by Rust)
    let mut node = head.as_mut();

    while let Some(this) = node {
        // Loop through every node that shares the same value as `this`
        loop {
            if let Some(ref mut next) = this.next {
                if this.val == next.val {
                    // `this` and `next` have the same value.
                    // Connect `this` to `next.next`, so that the
                    // list changes from:
                    //
                    //   ... -> this -> next -> next.next -> ...
                    //
                    // to:
                    //
                    //   ... -> this -> next.next -> ...
                    //
                    // The use of `take()` ensures that `next.next`
                    // is replaced with `None` (this avoids taking
                    // multiple ownerships).
                    this.next = next.next.take();
                    continue;
                }
            }
            // Either there's no next node, or the next node has a
            // different value than `this`
            break;
        }
        node = this.next.as_mut();
    }
}

fn delete_duplicates_4(head: &mut Option<Box<ListNode>>) {
    if head.is_none() {
        return;
    }
    let mut head = head.as_mut().unwrap();

    while let Some(ref n) = head.next {
        if head.val == n.val {
            head.next = head.next.take().unwrap().next;
        } else {
            head = head.next.as_mut().unwrap();
        }
    }
}

fn make_list(len: usize) -> ListNode {
    let mut a = 1;
    let mut b = 1;
    let mut list = ListNode::new(a);

    for _ in 0..len {
        let t = b;
        b = (a + b) % 10;
        a = t;
        list.push(a);
    }

    list
}

fn bench(len: usize) {
    let list = make_list(len);

    let N = 2048;

    println!("Bench Testing n = {}", len);
    {
        print!("    running delete_duplicates   . . . ");
        std::io::stdout().flush().unwrap();
        let mut dt = 0;
        for _ in 0..N {
            let list = Some(Box::new(list.clone()));
            let t0 = std::time::Instant::now();
            let _ = delete_duplicates(list).unwrap();
            dt += t0.elapsed().as_micros();
        }
        println!("{:>8}us", (dt as f64) / (N as f64));
    }
    {
        print!("    running delete_duplicates_2 . . . ");
        std::io::stdout().flush().unwrap();
        let mut dt = 0;
        for _ in 0..N {
            let list = Some(Box::new(list.clone()));
            let t0 = std::time::Instant::now();
            let _ = delete_duplicates_2(list).unwrap();
            dt += t0.elapsed().as_micros();
        }
        println!("{:>8}us", (dt as f64) / (N as f64));
    }
    {
        print!("    running delete_duplicates_3 . . . ");
        std::io::stdout().flush().unwrap();
        let mut dt = 0;
        for _ in 0..N {
            let mut list = Some(Box::new(list.clone()));
            let t0 = std::time::Instant::now();
            let _ = delete_duplicates_3(&mut list);
            dt += t0.elapsed().as_micros();
        }
        println!("{:>8}us", (dt as f64) / (N as f64));
    }
    {
        print!("    running delete_duplicates_3 . . . ");
        std::io::stdout().flush().unwrap();
        let mut dt = 0;
        for _ in 0..N {
            let mut list = Some(Box::new(list.clone()));
            let t0 = std::time::Instant::now();
            let _ = delete_duplicates_4(&mut list);
            dt += t0.elapsed().as_micros();
        }
        println!("{:>8}us", (dt as f64) / (N as f64));
    }
}

fn main() {
    for i in 5..=11 {
        bench(1 << i);
    }
}

Выход

Bench Testing n = 32
    running delete_duplicates   . . . 2.052734375us
    running delete_duplicates_2 . . . 2.16943359375us
    running delete_duplicates_3 . . . 0.0556640625us 
    running delete_duplicates_4 . . . 0.1826171875us
Bench Testing n = 64
    running delete_duplicates   . . . 4.1171875us
    running delete_duplicates_2 . . . 5.03515625us
    running delete_duplicates_3 . . . 0.33154296875us
    running delete_duplicates_4 . . . 0.06396484375us
Bench Testing n = 128
    running delete_duplicates   . . . 8.5419921875us
    running delete_duplicates_2 . . . 8.87158203125us
    running delete_duplicates_3 . . . 1.1669921875us
    running delete_duplicates_4 . . . 1.193359375us
Bench Testing n = 256
    running delete_duplicates   . . . 18.2841796875us
    running delete_duplicates_2 . . . 20.169921875us
    running delete_duplicates_3 . . . 2.74169921875us
    running delete_duplicates_4 . . . 2.35791015625us
Bench Testing n = 512
    running delete_duplicates   . . . 37.2880859375us
    running delete_duplicates_2 . . . 36.0595703125us
    running delete_duplicates_3 . . . 5.30224609375us
    running delete_duplicates_4 . . . 5.31103515625us
Bench Testing n = 1024
    running delete_duplicates   . . . 66.796875us
    running delete_duplicates_2 . . . 69.91552734375us
    running delete_duplicates_3 . . . 9.84814453125us
    running delete_duplicates_4 . . . 10.646484375us
Bench Testing n = 2048
    running delete_duplicates   . . . 133.638671875us
    running delete_duplicates_2 . . . 143.2666015625us
    running delete_duplicates_3 . . . 20.03955078125us
    running delete_duplicates_4 . . . 20.87939453125us