Detect if a Linked List is Circular in DSA Rust

Mental Model

A circular linked list loops back to an earlier node instead of ending with null. We want to find if such a loop exists.

Analogy: Imagine walking down a path that either ends or loops back to a previous spot. Detecting circularity is like noticing if you start revisiting the same place again and again.

1 -> 2 -> 3 -> 4 -> null

Circular:
1 -> 2 -> 3 -> 4 ->
          ↑       ↓
          ←-------

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4, with node 4 pointing back to node 2 (circular)

Goal: Detect if the linked list has a cycle (circular reference)

Step 1: Initialize two pointers: slow at 1, fast at 1

[slow->1] -> 2 -> 3 -> 4 -> (back to 2)
[fast->1] -> 2 -> 3 -> 4 -> (back to 2)

Why: Start both pointers at head to begin cycle detection

Step 2: Move slow by 1 step to 2, fast by 2 steps to 3

1 -> [slow->2] -> 3 -> 4 -> (back to 2)
1 -> 2 -> [fast->3] -> 4 -> (back to 2)

Why: Advance pointers at different speeds to detect cycle

Step 3: Move slow by 1 step to 3, fast by 2 steps: from 3 to 4, then back to 2

1 -> 2 -> [slow->3] -> 4 -> (back to 2)
1 -> [fast->2] -> 3 -> 4 -> (back to 2)

Why: Fast pointer loops back due to cycle, slow moves forward

Step 4: Move slow by 1 step to 4, fast by 2 steps: from 2 to 3, then to 4

1 -> 2 -> 3 -> [slow->4] -> (back to 2)
1 -> 2 -> [fast->4] -> (back to 2)

Why: Both pointers approach each other inside the cycle

Step 5: Move slow by 1 step back to 2 (due to cycle), fast by 2 steps: from 4 to 2, then to 3

1 -> [slow->2] -> 3 -> 4 -> (back to 2)
1 -> 2 -> [fast->3] -> 4 -> (back to 2)

Why: Pointers continue moving inside the cycle

Step 6: Move slow by 1 step to 3, fast by 2 steps: from 3 to 4, then back to 2

1 -> 2 -> [slow->3] -> 4 -> (back to 2)
1 -> [fast->2] -> 3 -> 4 -> (back to 2)

Why: Pointers are moving closer inside the cycle

Step 7: Move slow by 1 step to 4, fast by 2 steps: from 2 to 3, then to 4

1 -> 2 -> 3 -> [slow->4] -> (back to 2)
1 -> 2 -> 3 -> [fast->4] -> (back to 2)

Why: Pointers meet at node 4, confirming cycle

Result:

1 -> 2 -> 3 -> 4 -> (back to 2)
Cycle detected: true

Annotated Code

DSA Rust

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

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

impl Node {
    fn new(val: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node { val, next: None }))
    }
}

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 reached end, no cycle
        }
        let f_next_next = f_next.as_ref().unwrap().borrow().next.clone();
        if f_next_next.is_none() {
            return false; // fast reached end, no cycle
        }

        slow = s.borrow().next.clone(); // move slow by 1
        fast = f_next_next; // move fast by 2

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

fn main() {
    // Create nodes
    let n1 = Node::new(1);
    let n2 = Node::new(2);
    let n3 = Node::new(3);
    let n4 = Node::new(4);

    // Link nodes 1->2->3->4
    n1.borrow_mut().next = Some(n2.clone());
    n2.borrow_mut().next = Some(n3.clone());
    n3.borrow_mut().next = Some(n4.clone());

    // Create cycle: 4->2
    n4.borrow_mut().next = Some(n2.clone());

    let result = is_circular(Some(n1));
    println!("Cycle detected: {}", result);
}

while let (Some(s), Some(f)) = (slow.clone(), fast.clone()) {

loop while both pointers are valid to continue checking

if f_next.is_none() { return false; }

if fast pointer reaches end, no cycle

if f_next_next.is_none() { return false; }

if fast pointer's next next is none, no cycle

slow = s.borrow().next.clone();

move slow pointer by one step

fast = f_next_next;

move fast pointer by two steps

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

if slow and fast meet, cycle detected

Output

Cycle detected: true

Complexity Analysis

Time: O(n) because each node is visited at most twice by the two pointers

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Compared to using a hash set to store visited nodes (O(n) space), this uses constant space making it more efficient

Edge Cases

Empty list (head is None)

Returns false immediately as there is no cycle

DSA Rust

while let (Some(s), Some(f)) = (slow.clone(), fast.clone()) {

Single node with no cycle

Returns false because fast pointer reaches end quickly

DSA Rust

if f_next.is_none() { return false; }

Single node pointing to itself (cycle)

Returns true as slow and fast pointers meet immediately

DSA Rust

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

When to Use This Pattern

When you see a problem asking if a linked list loops back on itself, use the two-pointer (slow and fast) technique to detect cycles efficiently.

Common Mistakes

Mistake: Moving both pointers by one step instead of moving fast pointer by two steps
Fix: Move fast pointer two steps each iteration to detect cycle faster

Mistake: Not checking if fast or fast.next is None before moving pointers
Fix: Always check if fast and fast.next exist to avoid runtime errors

Summary

Detects if a linked list has a cycle by using two pointers moving at different speeds.

Use when you need to know if a linked list loops back to an earlier node.

If two pointers moving at different speeds meet, the list is circular.

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