Detect Cycle in Linked List Floyd's Algorithm in DSA Rust - Execution Trace

Concept Flow - Detect Cycle in Linked List Floyd's Algorithm

Start: slow=head, fast=head

↓

Move slow by 1 step

↓

Move fast by 2 steps

↓

Check if slow == fast?

No→fast or fast.next is None?

↓

Cycle detected

↓

Cycle detected

Two pointers move at different speeds through the list. If they meet, a cycle exists. If fast pointer reaches end, no cycle.

Execution Sample

DSA Rust

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

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

Execution Table

Step	Operation	slow Pointer	fast Pointer	Visual State
1	Initialize slow and fast at head	Node 10	Node 10	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ ... └────────┘ └────────┘ └────────┘ head slow, fast → Node 10
2	Move slow by 1 step	Node 20	Node 10	slow moves to Node 20 fast stays at Node 10 ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ ... └────────┘ └────────┘ └────────┘ head slow → Node 20 fast → Node 10
3	Move fast by 2 steps	Node 20	Node 30	fast moves to Node 30 ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ ... └────────┘ └────────┘ └────────┘ └────────┘ head slow → Node 20 fast → Node 30
4	Check slow == fast?	Node 20	Node 30	No match, continue slow != fast
5	Move slow by 1 step	Node 30	Node 30	slow moves to Node 30 ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ ... └────────┘ └────────┘ └────────┘ └────────┘ head slow → Node 30 fast → Node 30
6	Move fast by 2 steps	Node 30	Node 50	fast moves from Node 30 to Node 50 (two steps) ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ ... └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow → Node 30 fast → Node 50
7	Check slow == fast?	Node 30	Node 50	No match, continue slow != fast
8	Move slow by 1 step	Node 40	Node 50	slow moves to Node 40 ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ ... └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow → Node 40 fast → Node 50
9	Move fast by 2 steps	Node 40	Node 30	fast moves two steps: Node 50 → Node 30 (cycle back) Cycle formed: Node 50.next → Node 30 ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ ↑ | └─────────────────────────────┘ slow → Node 40 fast → Node 30
10	Check slow == fast?	Node 40	Node 30	No match, continue slow != fast
11	Move slow by 1 step	Node 50	Node 30	slow moves to Node 50 slow → Node 50 fast → Node 30
12	Move fast by 2 steps	Node 50	Node 50	fast moves two steps: Node 30 → Node 50 slow → Node 50 fast → Node 50
13	Check slow == fast?	Node 50	Node 50	Match found! Cycle detected

💡 slow and fast pointers meet at Node 50, confirming a cycle

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	Final
slow	Node 10	Node 20	Node 20	Node 30	Node 30	Node 40	Node 40	Node 50	Node 50	Node 50	Node 50	Node 50	Node 50	Node 50
fast	Node 10	Node 10	Node 30	Node 30	Node 50	Node 50	Node 30	Node 30	Node 50	Node 30	Node 30	Node 50	Node 50	Node 50

Key Moments - 3 Insights

Why do we move the fast pointer two steps but the slow pointer only one step?

Moving fast pointer two steps and slow pointer one step ensures that if a cycle exists, fast will eventually catch up to slow inside the cycle, as shown in steps 9 to 13 in the execution_table.

What happens if the list has no cycle?

If the list has no cycle, the fast pointer will reach the end (None) before slow and fast meet. This is checked in the while condition (fast.is_some() && fast.next.is_some()), stopping the loop safely.

Why do we check slow == fast after moving pointers?

We check slow == fast after moving pointers to detect if both pointers point to the same node, indicating a cycle. This is shown in steps 4, 7, 10, and finally at step 13 where they meet.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, where is the fast pointer?

A Node 30

B Node 50

C Node 40

D Node 20

💡 Hint

Check the 'fast Pointer' column at step 6 in the execution_table.

At which step do slow and fast pointers first point to the same node?

A Step 13

B Step 4

C Step 12

D Step 7

💡 Hint

Look for the first step where 'slow Pointer' equals 'fast Pointer' in the execution_table.

If the linked list had no cycle, what would happen to the fast pointer?

A It would meet slow pointer immediately

B It would keep moving forever

C It would eventually become None and stop the loop

D It would move only one step at a time

💡 Hint

Refer to the concept_flow and key_moments about loop termination conditions.

Concept Snapshot

Detect cycle using two pointers:
- slow moves 1 step
- fast moves 2 steps
- if slow == fast, cycle exists
- if fast reaches end (None), no cycle
- efficient O(n) time, O(1) space
- also called Floyd's Tortoise and Hare algorithm

Full Transcript

This concept uses two pointers, slow and fast, starting at the head of the linked list. Slow moves one node at a time, fast moves two nodes at a time. If the list has a cycle, fast will eventually catch up to slow inside the cycle. If the list has no cycle, fast will reach the end (None) and the loop stops. We check after each move if slow and fast point to the same node to detect the cycle. This method is called Floyd's Cycle Detection Algorithm and is efficient in time and space.

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