Testing Cycle in a Linked List

help
1

Hello Everyone,

I have an implementation for a problem: Detect Cycle in a Linked List and would like to test it. An online judge for this question is not available on that website.

My implementation is:

src/linked_list/list_node.rs

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

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

pub struct Solution;

and src/linked_list/detect_cycle.rs

use crate::linked_list::list_node::*;

impl Solution {
    fn detect_cycle(head: Option<Box<ListNode>>) -> bool {
        let mut slow = head.as_ref();
        let mut fast = head.as_ref();
        let mut cycle_exists = false;

        while let (Some(walker), Some(runner)) = (slow, fast) {
            slow = walker.next.as_ref();
            fast = runner.next.as_ref();

            if slow == fast {
                cycle_exists = true;
                break;
            }
        }

        cycle_exists
    }
}

How do I write a test case for the first example - head = [3,2,0,-4], and a cycle exists in which the tail node connects to the second node 2 ?

2

Given this definition:

A correct solution would be to simply return false unconditionally— Box is an exclusive owning pointer, so it’s impossible for you to have any cycles without having already triggered UB. At which point, you can expect your cycle detection code to malfunction anyway.

6 Likes
3

Box is an exclusive owning pointer, so it’s impossible for you to have any cycles without having already triggered UB. At which point, you can expect your cycle detection code to malfunction anyway.

I don't understand this clearly. Could you elaborate ?

Other questions in this topic have the same structure for ListNode. If I change the structure of ListNode to:

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

would I be able to test it ?

4

It’s impossible by design to have two Boxes that point to the same memory: Box<T> has essentially the same semantics as holding a T directly, except that it solves some layout problems (i.e. dynamically-sized values and infinite-sized recursive types).

2 Likes
5

Yes, multiple Rc instances can point to the same allocation, so you can create a cycle with that type.

2 Likes
6

Linked List is hard in Rust ...

I cannot solve this gracefully, but I may put a link here Learn Rust With Entirely Too Many Linked Lists .

7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.