A simple algorithmic problem, but when i want to solve it by rust, i am fall in trouble.
This is my code:
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>,
}
impl ListNode {
#[inline]
fn new(val: i32) -> Self {
ListNode { next: None, val }
}
}
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match head {
Some(node) => {
let mut value = node.val;
let mut ptr = &mut node;
while let Some(mut n) = &ptr.next {
if value == n.val {
ptr.next = n.next.clone();
} else {
value = n.val;
// problem in right here.
// the error of complier : E0308: mismatched types expected mutable reference, found struct `std::boxed::Box` note: expected type `&mut std::boxed::Box<ListNode>`found type `std::boxed::Box<ListNode>`
// i know it what is meaning, but i can't solve it.
ptr = n;
}
}
Some(node)
}
None => None,
}
}
because once you take read-only & reference, nothing can make it mutable (that mut n means assignment to n, not to ptr, so you can do n = something_else, but can't change *n).
but mutable in Rust also means exclusive, so if you do:
while let Some(mut n) = &mut ptr.next {
for the scope of while {}, all of ptr is locked to offer exclusive access to n, so you will get borrow checking errors if you try to modify ptr.next, because that violates exclusivity - it would modify n indirectly.
I fudged it horribly by using map chains that limit borrow to 1 line only:
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match head {
Some(mut node) => {
let mut value = node.val;
let mut ptr = &mut node;
while ptr.next.is_some() {
if ptr.next.as_ref().map_or(false, |n| value == n.val) {
ptr.next = ptr.next.as_mut().and_then(|n| n.next.take());
} else {
value = ptr.next.as_ref().unwrap().val;
ptr = ptr.next.as_mut().unwrap();
}
}
Some(node)
}
None => None,
}
}
It's worth noting that writing linked lists is surprisingly tricky in safe Rust. There's a very good online book on this called 'Learning Rust With Entirely Too Many Linked Lists', which is definitely worth a read.
This is one of those things that cannot be written iteratively without a whole bunch of unwraps because we otherwise get overlapping mutable references. If you are okay with recursion you can avoid all the unwraps like this:
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
fn inner(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
let mut head = head?;
if head.val == val {
inner(head.next, val)
} else {
head.next = inner(head.next, head.val);
Some(head)
}
}
let mut head = head?;
head.next = inner(head.next, head.val);
Some(head)
}