Detect if a Linked List is Circular in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Circular Linked List Detection Function

What is the output of the following Rust code that checks if a linked list is circular?

DSA Rust

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

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

fn is_circular(head: Option<Rc<RefCell<Node>>>) -> bool {
    let mut slow = head.clone();
    let mut fast = head.clone();

    while let (Some(s), Some(f)) = (slow.clone(), fast.clone()) {
        let f_next = f.borrow().next.clone();
        if f_next.is_none() {
            return false;
        }
        fast = f_next.unwrap().borrow().next.clone();
        slow = s.borrow().next.clone();

        if slow.is_some() && fast.is_some() && Rc::ptr_eq(slow.as_ref().unwrap(), fast.as_ref().unwrap()) {
            return true;
        }
    }
    false
}

fn main() {
    let node1 = Rc::new(RefCell::new(Node { value: 1, next: None }));
    let node2 = Rc::new(RefCell::new(Node { value: 2, next: None }));
    let node3 = Rc::new(RefCell::new(Node { value: 3, next: None }));

    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());
    node3.borrow_mut().next = Some(node1.clone()); // Circular link

    println!("{}", is_circular(Some(node1)));
}

A Runtime panic

B false

C Compilation error

D true

💡 Hint

Think about how the fast and slow pointers move and meet in a circular linked list.

The code uses Floyd's cycle detection algorithm. Since node3 points back to node1, the list is circular, so the function returns true.

❓ Predict Output

intermediate

Output when Linked List is Not Circular

What will the output be when the linked list has no cycle in the following Rust code?

DSA Rust

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

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

fn is_circular(head: Option<Rc<RefCell<Node>>>) -> bool {
    let mut slow = head.clone();
    let mut fast = head.clone();

    while let (Some(s), Some(f)) = (slow.clone(), fast.clone()) {
        let f_next = f.borrow().next.clone();
        if f_next.is_none() {
            return false;
        }
        fast = f_next.unwrap().borrow().next.clone();
        slow = s.borrow().next.clone();

        if slow.is_some() && fast.is_some() && Rc::ptr_eq(slow.as_ref().unwrap(), fast.as_ref().unwrap()) {
            return true;
        }
    }
    false
}

fn main() {
    let node1 = Rc::new(RefCell::new(Node { value: 1, next: None }));
    let node2 = Rc::new(RefCell::new(Node { value: 2, next: None }));
    let node3 = Rc::new(RefCell::new(Node { value: 3, next: None }));

    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());
    node3.borrow_mut().next = None; // No cycle

    println!("{}", is_circular(Some(node1)));
}

A false

B Compilation error

C Runtime panic

D true

💡 Hint

If the fast pointer reaches the end, the list is not circular.

Since node3's next is None, the fast pointer reaches the end and the function returns false.

🔧 Debug

advanced

Identify the Bug in Circular Linked List Detection

What error will the following Rust code produce when trying to detect a cycle in a linked list?

DSA Rust

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

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

fn is_circular(head: Option<Rc<RefCell<Node>>>) -> bool {
    let mut slow = head.clone();
    let mut fast = head.clone();

    while fast.is_some() && fast.as_ref().unwrap().borrow().next.is_some() {
        slow = slow.unwrap().borrow().next.clone();
        fast = fast.unwrap().borrow().next.clone().unwrap().borrow().next.clone();

        if slow.is_some() && fast.is_some() && Rc::ptr_eq(slow.as_ref().unwrap(), fast.as_ref().unwrap()) {
            return true;
        }
    }
    false
}

fn main() {
    let node1 = Rc::new(RefCell::new(Node { value: 1, next: None }));
    let node2 = Rc::new(RefCell::new(Node { value: 2, next: None }));
    let node3 = Rc::new(RefCell::new(Node { value: 3, next: None }));

    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());
    node3.borrow_mut().next = None;

    println!("{}", is_circular(Some(node1)));
}

A Compilation error due to borrow checker

B Returns false correctly

C Returns true incorrectly

D panic at unwrap on None value

💡 Hint

Check how unwrap is used and if fast pointer always has next nodes.

The code safely checks fast and fast.next before unwrap, so no panic occurs. The list is not circular, so it returns false correctly.

🧠 Conceptual

advanced

Why Use Two Pointers to Detect Circular Linked List?

Why does Floyd's cycle detection algorithm use two pointers moving at different speeds to detect a cycle in a linked list?

A Because two pointers reduce memory usage compared to storing visited nodes

B Because it sorts the linked list while detecting cycles

C Because the fast pointer will eventually catch the slow pointer if there is a cycle

D Because it reverses the linked list to find cycles

💡 Hint

Think about how two runners on a circular track eventually meet.

The fast pointer moves two steps and the slow pointer moves one step. If a cycle exists, they will meet inside the loop.

❓ Predict Output

expert

Output of Circular Linked List Detection with Self-Loop Node

What is the output of the following Rust code where a node points to itself, forming a self-loop?

DSA Rust

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

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

fn is_circular(head: Option<Rc<RefCell<Node>>>) -> bool {
    let mut slow = head.clone();
    let mut fast = head.clone();

    while let (Some(s), Some(f)) = (slow.clone(), fast.clone()) {
        let f_next = f.borrow().next.clone();
        if f_next.is_none() {
            return false;
        }
        fast = f_next.unwrap().borrow().next.clone();
        slow = s.borrow().next.clone();

        if slow.is_some() && fast.is_some() && Rc::ptr_eq(slow.as_ref().unwrap(), fast.as_ref().unwrap()) {
            return true;
        }
    }
    false
}

fn main() {
    let node1 = Rc::new(RefCell::new(Node { value: 1, next: None }));

    node1.borrow_mut().next = Some(node1.clone()); // Self-loop

    println!("{}", is_circular(Some(node1)));
}

A true

B false

C Compilation error

D Runtime panic

💡 Hint

A node pointing to itself forms a cycle of length one.

The slow and fast pointers both start at the same node and meet immediately, so the function returns true.

Practice

1. What does it mean if a linked list is circular?

easy

A. The linked list has no nodes

B. The linked list contains only one node

C. The linked list nodes are sorted in ascending order

D. The last node points back to one of the previous nodes, forming a loop

Solution

1. Step 1: Understand linked list structure

   A linked list is a chain of nodes where each node points to the next node.

2. Step 2: Define circular linked list

   If the last node points back to any previous node, it creates a loop, making the list circular.

3. Final Answer:

   The last node points back to one of the previous nodes, forming a loop -> Option D

4. Quick Check:

   Circular linked list = last node points back [OK]

Hint: Circular means last node links back to earlier node [OK]

Common Mistakes:

• Thinking circular means sorted
• Confusing empty list with circular
• Assuming single node list is always circular

2. Which Rust code snippet correctly defines a singly linked list node struct?

easy

A. struct Node { value: i32, next: Option }

B. struct Node { value: i32, next: Node }

C. struct Node { value: i32, next: &Node }

D. struct Node { value: i32, next: Box<Node> }

Solution

1. Step 1: Understand Rust ownership for linked lists

   Rust requires using Option for next to allow nullable and heap allocation.

2. Step 2: Check each option

   struct Node { value: i32, next: Option } uses Option, which is correct. Others either lack Option or use references incorrectly.

3. Final Answer:

   struct Node { value: i32, next: Option } -> Option A

4. Quick Check:

   Use Option for next pointer in Rust [OK]

Hint: Use Option for next pointer in Rust [OK]

Common Mistakes:

• Using raw Node type for next causes infinite size error
• Using references without lifetimes
• Omitting Option for nullable next

3. Given the following Rust code to detect a circular linked list, what will be printed?

fn is_circular(head: &Option) -> bool {
    let mut slow = head.as_ref();
    let mut fast = head.as_ref();
    while let (Some(s), Some(f)) = (slow, fast) {
        fast = f.next.as_ref().and_then(|n| n.next.as_ref());
        slow = s.next.as_ref();
        if slow == fast {
            return true;
        }
    }
    false
}

// List: 1 -> 2 -> 3 -> 2 (loop back to node with value 2)
// Calling is_circular returns what?

medium

A. false

B. true

C. Compilation error

D. Infinite loop

Solution

1. Step 1: Understand Floyd's cycle detection

   Two pointers move at different speeds; if they meet, list is circular.

2. Step 2: Analyze given list and code

   List loops back from node 3 to node 2, so slow and fast pointers will meet, returning true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Floyd's algorithm detects loop = true [OK]

Hint: Floyd's cycle detection returns true if pointers meet [OK]

Common Mistakes:

• Confusing pointer movement speeds
• Not checking both pointers for null
• Assuming no loop when pointers meet

4. Identify the bug in this Rust function that tries to detect a circular linked list:

fn has_cycle(head: &Option) -> bool {
    let mut slow = head.as_ref();
    let mut fast = head.as_ref();
    while fast.is_some() && fast.unwrap().next.is_some() {
        slow = slow.unwrap().next.as_ref();
        fast = fast.unwrap().next.as_ref().unwrap().next.as_ref();
        if slow == fast {
            return true;
        }
    }
    false
}

medium

A. Function always returns false due to wrong loop condition

B. Pointers move at the same speed, so no cycle detection

C. Using unwrap() without checking can cause panic if null

D. Missing return type causes compilation error

Solution

1. Step 1: Check unwrap usage safety

   Using unwrap() without confirming Some can panic if null is encountered.

2. Step 2: Identify risk in loop

   fast.unwrap().next.as_ref().unwrap() assumes next exists, which may not be true at list end.

3. Final Answer:

   Using unwrap() without checking can cause panic if null -> Option C

4. Quick Check:

   Unsafe unwrap causes panic [OK]

Hint: Avoid unwrap without checking Option first [OK]

Common Mistakes:

• Ignoring unwrap panic risk
• Assuming pointers move same speed
• Not checking loop exit conditions

5. You have a linked list where the last node's next pointer is mistakenly set to itself, creating a single-node loop. How should you modify the Rust cycle detection function to correctly detect this case?

hard

A. Use a hash set to store visited nodes and detect repeats

B. Ignore cases where next points to itself, treat as non-circular

C. Only check if fast pointer reaches null to decide no cycle

D. Check if slow and fast pointers meet even if they start at the same node

Solution

1. Step 1: Understand single-node loop problem

   If a node points to itself, Floyd's algorithm may detect cycle, but edge cases can be tricky.

2. Step 2: Use hash set for robust detection

   Storing visited nodes in a hash set helps detect any repeated node, including self-loop cases.

3. Final Answer:

   Use a hash set to store visited nodes and detect repeats -> Option A

4. Quick Check:

   Hash set detects all cycles including self-loops [OK]

Hint: Use hash set to catch all loops including self-pointing nodes [OK]

Common Mistakes:

• Assuming Floyd's algorithm covers all edge cases
• Ignoring self-loop as cycle
• Not handling single-node circular lists