Two pointers to a naïve linked list

[San]

For purely didactic purposes I'm dealing with a singly linked list.

I'm aware that working with this particular type of data structure in Rust
requires a certain understanding of many core concepts (beautifully presented
in "Learning Rust With Entirely Too Many Linked Lists" as well as in this
forum) but still I cannot see what I'm missing to reach a working solution.

The problem is a classic: find a loop in a singly linked list.

The list is defined as:

use std::cell::Ref;
use std::cell::RefCell;
use std::rc::Rc;

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

The test I would like to pass is:

#[cfg(test)]
mod tests {
    use super::*;
    
    #[test]
    fn has_cycle() {
        // Define a list with a loop (n2 -> n0).
        let n0 = Rc::new(RefCell::new(ListNode { val: 0, next: None }));
        let n1 = Rc::new(RefCell::new(ListNode { val: 0, next: None }));
        let n2 = Rc::new(RefCell::new(ListNode { val: 0, next: None }));

        n0.borrow_mut().next = Some(Rc::clone(&n1));
        n1.borrow_mut().next = Some(Rc::clone(&n2));
        n2.borrow_mut().next = Some(Rc::clone(&n0));

        let list = Some(n0);
        assert_eq!(super::has_cycle(list), true);
    }
}

I was thinking of solving the problem with 2 "pointers": a slow one that
moves of 1 node at the time, and a fast one, that moves of 2 nodes at the
time. If there is a loop the 2 pointers will eventually meet, otherwise a None
is found.

I tried to define a "single" iterator as follows; please note that the type
definitions are explicit only for a better/personal understanding and that
the implementation is just partial:

pub fn has_cycle(head: Option<Rc<RefCell<ListNode>>>) -> bool {
    let mut slow: Option<Rc<RefCell<ListNode>>> = head;

    loop {
        let nxt: Rc<RefCell<ListNode>> = slow.unwrap();
        let l: Ref<ListNode> = nxt.borrow();
        if let Some(n) = &l.next {
            let next: Rc<RefCell<ListNode>> = Rc::clone(n);
            slow = Some(next)
        } else {
            break;
        }
    }

    // ... a lot of logic is missing

    false
}

This compile correctly but clearly I cannot define a second "iterator" after
slow in the same way. So I considered using as_ref:

let mut slow: Option<&Rc<RefCell<ListNode>>> = head.as_ref();
let mut fast: Option<&Rc<RefCell<ListNode>>> = head.as_ref();

But I ended up not being able to update the next in the loop. I also tried
to use a match:

loop {
    match slow {
        None => break,
        Some(n) => {
            let n: Ref<ListNode> = n.borrow();
            slow = n.next.as_ref();
        }
    }
}

but this obviously breaks the borrowing rules:

slow = n.next.as_ref();
       ^ borrowed value does not live long enough

So my question(s):

• am I too naive in tackling this problem with this approach?
• is my understanding of Rc and RefCell "misplaced" in this context?

Thank you so much in advance.

[alice]

Remember that RefCell uses runtime counters to ensure that the borrowing rules are enforced. This means that when you call borrow on a RefCell and obtain a Ref, that reference type has a destructor which decrements the counter on drop. If you try to keep around a borrow to the Ref into the next iteration while dropping the Ref itself, your code will fail to compile as you're using the data after decreasing the counter.

The reason your original loop worked is because you used Rc::clone to create a new independent handle to the node, which allows you to drop the Ref and release the lock.

[San]

Thank you Alice: your observation is on point.

I resort to borrow() from the RefCell to access its content.
I feel like bouncing back and forth a Ref and a value due to the idea of using the 2 "iterators" with the signature:

let mut slow: Option<&Rc<RefCell<ListNode>>> = head.as_ref();
let mut fast: Option<&Rc<RefCell<ListNode>>> = head.as_ref();

It seems a wrong choice since at every iteration I'm (mistakenly) trying to keep a reference in a way or another (here a very verbose trace of my thinking):

loop {
    match slow {
        None => break,
        Some(node) => {
            let node: &Rc<RefCell<ListNode>> = node;
            let node: Rc<RefCell<ListNode>> = Rc::clone(node);
            let next: &Option<Rc<RefCell<ListNode>>> = &node.borrow().next;
            let next: &Rc<RefCell<ListNode>> = next.as_ref().unwrap();
            let next: Rc<RefCell<ListNode>> = Rc::clone(next);
            slow = Some(&next);
        }
    }
}

I cannot take() the Option because of the two iterators.
I start thinking that this approach is simply wrong here.

[alice]

This time it fails because Some(&next) is a reference to the last next binding, which goes out of scope at the end of the match, invalidating the reference. Prefer an Option<Rc<...>> instead.

[San]

I see, which is also the reason why I suspect that using a Option<&...> in the loop is not a good choice:
it feels like forcing the same approach and no matter what I end up taking as_ref().

loop {
    match slow {
        None => break,
        Some(node) => {
            let node: &Rc<RefCell<ListNode>> = node;
            let node: Rc<RefCell<ListNode>> = Rc::clone(node);
            let next: &Option<Rc<RefCell<ListNode>>> = &node.borrow().next;
            let next: &Rc<RefCell<ListNode>> = next.as_ref().unwrap();
            let next: Rc<RefCell<ListNode>> = Rc::clone(next);
            let next: Option<Rc<RefCell<ListNode>>> = Some(next);
            let next: Option<&Rc<RefCell<ListNode>>> = next.as_ref();
            slow = next;
        }
    }
}

That has the same expected result:

 = next.as_ref();
   ^^^^ borrowed value does not live long enough

Thank you for your patience.

[alice]

Yes, in this case the new value for slow borrows from the second-to-last next, which also goes out of scope at the end of the match.

[San]

I see, this confirms my understanding.
I will explore other approaches that do not involve taking a reference.

Thank you.

[Yandros]

You can use Cell<Option<Rc< ListNode >>> for your next field, with the following helper(s):

impl ListNode {
    fn get_next (&self) -> Option<Rc<ListNode>>
    {
        let next = self.take_next()?;
        self.set_next(next.clone());
        Some(next)
    }
    // where
    fn set_next (&self, next: Rc<ListNode>)
    {
        self.next.set(Some(next));
    }
    fn take_next (&self) -> Option<Rc<ListNode>>
    {
        self.next.replace(None);
    }
}

This way you are guaranteed to never panic

[San]

Thank you so much Yandros and thank you alice as well.

The implementation of get_next really "clicked" my understanding of `Rc.