A problem about pointer

help
1

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

i need help, who can help me?

2

The problem starts at:

while let Some(mut n) = &ptr.next {

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

I'm sure there's a more elegant solution…

2 Likes
3

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.

3 Likes
4

thanks very much. but i still have some small puzzles. i can't understand the below very clearly

ptr.next = ptr.next.as_mut().and_then(|n| n.next.take());

the difference between as_mut() and &mut pter.next?

5

I have read it, but something is difficult for me especially after Chapter4. i need to keep learning , thanks.

6

That line is equivalent to:

ptr.next = match &mut ptr.next {
   Some(next) => next.take(),
   None => None,
}

and take() is a nice function that replaces target with None and gives you what has been in there before.

The useful thing about that as_mut() is that it's a 1-liner, and borrows ptr.next just for that expression, not for entire scope.

7

Does this work:

pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut node = head?;

    while node.val == node.next.as_ref()?.val {
        node.next = node.next?.next;
    }
    
    node.next = delete_duplicates(node.next.take());
    
    Some(node)
}

?

(Do you have any ready testing code? Otherwise I'll test it myself)

1 Like
8

well, i have understand. thank you. Should i closed this topic like the Github?

9

thank you , this is a different solution way. i will try it.

10

I tested it myself and there was a bug in my code. This would be right:

pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut node = head?;

    while node.next.is_some() && node.val == node.next.as_ref().unwrap().val {
        node.next = node.next.unwrap().next;
    }

    node.next = delete_duplicates(node.next.take());

    Some(node)
}
11

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

Playground

1 Like
12

On the other hand, recursive solution on unbounded input is a stack overflow waiting to happen.

I'll better go with unwrap.

fn delete_duplicates(list: &mut Option<Box<ListNode>>) {
    if let Some(mut node) = list.as_mut() {
        while let Some(mut rest) = node.next.take() {
            while rest.val == node.val {
                if let Some(tail) = rest.next {
                    rest = tail;
                } else {
                    return;
                }
            };
            node.next = Some(rest);
            node = node.next.as_mut().unwrap();
        }
    }
}

Playground

Edited to add: derived implementation of Drop is recursive too, so the code requires further elaboration:

Playground

13

That's probably one of the many reasons why linked lists in Rust are not a good idea in production :wink: (but they are great for learning)

14

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.