 # Two pointers to a naïve linked list

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.

1 Like

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.

1 Like

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.

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.

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
``````

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.

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

Thank you.

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

1 Like

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

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

1 Like