Detect Cycle in Linked List Floyd's Algorithm in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floyd's Cycle Detection on a cyclic linked list

What is the output of this Rust code that uses Floyd's algorithm to detect a cycle in a linked list?

DSA Rust

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

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

fn has_cycle(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() && slow == fast {
            return true;
        }
    }
    false
}

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

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

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

A false

B Runtime panic

C true

D Compilation error

💡 Hint

Think about what happens when the fast pointer moves two steps and the slow pointer moves one step in a cycle.

The code creates a linked list with a cycle by linking the last node back to the first node. Floyd's algorithm uses two pointers moving at different speeds. When there is a cycle, the fast pointer will eventually meet the slow pointer, so the function returns true.

❓ Predict Output

intermediate

Output of Floyd's Cycle Detection on an acyclic linked list

What is the output of this Rust code that uses Floyd's algorithm to detect a cycle in a linked list without a cycle?

DSA Rust

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

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

fn has_cycle(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() && slow == fast {
            return true;
        }
    }
    false
}

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

    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());
    // no cycle created

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

A false

B true

C Compilation error

D Runtime panic

💡 Hint

If the fast pointer reaches the end of the list, what does that mean about cycles?

The linked list has no cycle because the last node's next is None. The fast pointer reaches the end without meeting the slow pointer, so the function returns false.

🔧 Debug

advanced

Identify the error in this Floyd's cycle detection implementation

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

DSA Rust

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

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

        if slow == fast {
            return true;
        }
    }
    false
}

struct Node {
    val: i32,
    next: Option<Box<Node>>,
}

A Compilation error due to move of 'head' into 'slow' and 'fast'

B Runtime panic due to unwrap on None

C Logical error: always returns false even if cycle exists

D No error, returns correct result

💡 Hint

Consider ownership and moves when assigning 'head' to 'slow' and 'fast'.

The code tries to assign 'head' to both 'slow' and 'fast', but 'head' is moved into 'slow' on the first assignment, so the second assignment to 'fast' causes a compilation error because 'head' is no longer available.

🧠 Conceptual

advanced

Why does Floyd's algorithm detect cycles efficiently?

Which of the following best explains why Floyd's cycle detection algorithm can detect a cycle in a linked list efficiently?

A It marks visited nodes by changing their values to detect revisits.

B It uses two pointers moving at different speeds; if a cycle exists, they will meet inside the cycle.

C It uses extra memory to store visited nodes and checks for repeats.

D It reverses the linked list and checks if the head changes.

💡 Hint

Think about how two pointers moving at different speeds behave in a cycle.

Floyd's algorithm uses two pointers moving at different speeds (slow and fast). If there is a cycle, the fast pointer will eventually catch up to the slow pointer inside the cycle, confirming its presence without extra memory.

❓ Predict Output

expert

Output of Floyd's algorithm on a complex linked list with cycle starting mid-list

What is the output of this Rust code that detects a cycle in a linked list where the cycle starts at the third node?

DSA Rust

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

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

fn has_cycle(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() && slow == fast {
            return true;
        }
    }
    false
}

fn main() {
    let node1 = Rc::new(RefCell::new(Node { val: 1, next: None }));
    let node2 = Rc::new(RefCell::new(Node { val: 2, next: None }));
    let node3 = Rc::new(RefCell::new(Node { val: 3, next: None }));
    let node4 = Rc::new(RefCell::new(Node { val: 4, next: None }));
    let node5 = Rc::new(RefCell::new(Node { val: 5, next: None }));

    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());
    node3.borrow_mut().next = Some(node4.clone());
    node4.borrow_mut().next = Some(node5.clone());
    node5.borrow_mut().next = Some(node3.clone()); // cycle starts at node3

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

A Compilation error

B Runtime panic

C false

D true

💡 Hint

The cycle starts at node 3, so the fast and slow pointers will meet inside the cycle.

The linked list has a cycle starting at node 3. Floyd's algorithm detects this by the fast pointer eventually catching the slow pointer inside the cycle, so the function returns true.

Practice

1. What is the main idea behind Floyd's Cycle Detection Algorithm in a linked list?

easy

A. Use two pointers moving at different speeds to detect a cycle

B. Count the number of nodes and check if it exceeds a limit

C. Reverse the linked list and check if it matches the original

D. Use a hash set to store visited nodes and check for repeats

Solution

1. Step 1: Understand Floyd's algorithm concept

   It uses two pointers, one moving faster (fast) and one slower (slow) through the list.

2. Step 2: Detect cycle by pointer meeting

   If the fast pointer meets the slow pointer, a cycle exists; otherwise, no cycle.

3. Final Answer:

   Use two pointers moving at different speeds to detect a cycle -> Option A

4. Quick Check:

   Two pointers at different speeds = cycle detection [OK]

Hint: Two pointers at different speeds detect cycle fast [OK]

Common Mistakes:

• Thinking counting nodes detects cycle
• Assuming reversing list helps detect cycle
• Using extra memory instead of pointers

2. Which Rust code snippet correctly initializes the slow and fast pointers for Floyd's cycle detection in a linked list named head?

easy

A. let mut slow = head.as_ref(); let mut fast = head.as_ref();

B. let mut slow = head.clone(); let mut fast = head.clone();

C. let mut slow = &head.next; let mut fast = &head.next.next;

D. let mut slow = &head; let mut fast = &head.next;

Solution

1. Step 1: Initialize both pointers at head

   Floyd's algorithm starts both slow and fast pointers at the head node.

2. Step 2: Correct Rust reference usage

   Using head.as_ref() for both slow and fast is correct; fast moves faster later.

3. Final Answer:

   let mut slow = head.as_ref(); let mut fast = head.as_ref(); -> Option A

4. Quick Check:

   Both pointers start at head [OK]

Hint: Start both pointers at head node [OK]

Common Mistakes:

• Starting fast pointer at head.next before loop
• Cloning nodes unnecessarily
• Using wrong references causing borrow errors

3. What will be the output of the following Rust code snippet detecting a cycle in a linked list?

struct Node { val: i32, next: Option }

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.map(|n| n as *const ()) == fast.map(|n| n as *const ()) {
            return true;
        }
    }
    false
}

// List: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node with value 2)

medium

A. Infinite loop

B. false

C. true

D. Compilation error

Solution

1. Step 1: Understand the list structure

   The list has a cycle starting at node with value 2, so cycle exists.

2. Step 2: Trace Floyd's pointers

   Slow and fast pointers will eventually meet inside the cycle, returning true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Cycle present = true [OK]

Hint: Cycle in list means pointers meet = true [OK]

Common Mistakes:

• Assuming no cycle returns true
• Confusing Option with references
• Missing unwrap() causing panic

4. Identify the bug in this Rust code snippet for detecting a cycle using Floyd's algorithm:

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(); // Bug here
        if slow.map(|n| n as *const ()) == fast.map(|n| n as *const ()) {
            return true;
        }
    }
    false
}

medium

A. slow pointer moves two steps instead of one

B. fast pointer moves only one step instead of two

C. Missing check for slow being None

D. Incorrect comparison of slow and fast pointers

Solution

1. Step 1: Analyze fast pointer movement

   Fast pointer should move two steps each loop, but here it moves only one step.

2. Step 2: Understand impact on cycle detection

   Moving fast only one step breaks Floyd's logic, so cycle detection fails or slows.

3. Final Answer:

   fast pointer moves only one step instead of two -> Option B

4. Quick Check:

   Fast pointer must move two steps [OK]

Hint: Fast pointer must jump two nodes each iteration [OK]

Common Mistakes:

• Moving fast pointer one step only
• Not checking fast pointer's next before moving
• Comparing pointers incorrectly

5. Given a linked list where the last node points back to the head (forming a cycle), how can you modify Floyd's algorithm to find the exact node where the cycle begins?

hard

A. Use a hash set to store nodes and find first repeated node

B. Count nodes until slow and fast meet, then return that count as cycle start

C. Reverse the list and check where reversal breaks

D. After detecting cycle, reset slow to head and move both pointers one step until they meet

Solution

1. Step 1: Detect cycle using Floyd's algorithm

   First, detect if cycle exists by moving slow and fast pointers.

2. Step 2: Find cycle start node

   Reset slow to head, then move slow and fast one step each until they meet; meeting point is cycle start.

3. Final Answer:

   After detecting cycle, reset slow to head and move both pointers one step until they meet -> Option D

4. Quick Check:

   Reset slow and move both pointers to find cycle start [OK]

Hint: Reset slow to head after cycle detection to find start [OK]

Common Mistakes:

• Trying to count nodes instead of pointer moves
• Using extra memory instead of pointer reset
• Reversing list which breaks cycle detection