Detect Cycle in Linked List Floyd's Algorithm in DSA Rust - Deep Dive

Overview - Detect Cycle in Linked List Floyd's Algorithm

What is it?

Detecting a cycle in a linked list means finding out if the list loops back on itself instead of ending. Floyd's Algorithm uses two pointers moving at different speeds to check if they meet inside the list, which shows a cycle. This method is efficient and does not need extra memory. It helps avoid infinite loops when working with linked lists.

Why it matters

Without detecting cycles, programs can get stuck forever when processing linked lists that loop back. This can cause crashes or freezes in software. Floyd's Algorithm solves this by quickly finding cycles without extra space, making programs safer and faster. It is widely used in real systems to ensure data structures behave correctly.

Where it fits

Before learning this, you should understand what linked lists are and how pointers work. After this, you can learn about removing cycles or finding the start of the cycle. This topic fits into the broader study of linked list algorithms and pointer manipulation.

Mental Model

Core Idea

If two pointers move through a linked list at different speeds, they will meet inside a cycle if one exists.

Think of it like...

Imagine two runners on a circular track: one runs faster than the other. If the track loops, the faster runner will eventually catch up to the slower one.

Linked List Nodes:
[1] -> [2] -> [3] -> [4] -> [5]
                     ↑         ↓
                     ←---------

Pointers:
Slow moves one step at a time
Fast moves two steps at a time
They meet inside the loop if cycle exists

Build-Up - 7 Steps

1

Foundation

Understanding Linked Lists Basics

Concept: Learn what a linked list is and how nodes connect using pointers.

A linked list is a chain of nodes where each node points to the next. The last node points to null if no cycle exists. Each node holds data and a pointer to the next node.

Result

You can visualize a linked list as a chain of boxes connected by arrows, ending with a null pointer.

Knowing how nodes link together is essential to understand how cycles form and how pointers move through the list.

2

Foundation

What is a Cycle in Linked List

Concept: A cycle happens when a node points back to a previous node, creating a loop.

Instead of the last node pointing to null, it points to an earlier node. This means traversing the list can go on forever if not detected.

Result

The linked list no longer ends; it loops back creating an infinite path.

Recognizing cycles is crucial to prevent infinite loops in algorithms that traverse linked lists.

3

Intermediate

Two Pointer Technique Introduction

Concept: Use two pointers moving at different speeds to detect cycles.

Start two pointers at the head. Move one pointer (slow) one step at a time, and the other (fast) two steps at a time. If the fast pointer reaches null, no cycle exists.

Result

If pointers never meet and fast reaches null, the list has no cycle.

Using two pointers at different speeds cleverly detects cycles without extra memory.

4

Intermediate

Detecting Cycle with Floyd's Algorithm

🤔Before reading on: do you think the pointers meet only if a cycle exists, or can they meet even without a cycle? Commit to your answer.

Concept: If a cycle exists, the fast pointer will eventually catch the slow pointer inside the loop.

Because the fast pointer moves faster, it laps the slow pointer inside the cycle. When they meet, a cycle is confirmed. If fast reaches null, no cycle.

Result

Meeting of pointers means cycle detected; no meeting means no cycle.

Understanding pointer speeds and meeting conditions is key to Floyd's cycle detection.

5

Intermediate

Rust Implementation of Floyd's Algorithm

Concept: Write Rust code to implement the two-pointer cycle detection.

Define a linked list node struct with Option> for next. Use two mutable references for slow and fast pointers. Move slow by one and fast by two steps in a loop. Return true if they meet, false if fast reaches None.

Result

The function returns true if a cycle exists, false otherwise.

Implementing in Rust teaches safe pointer handling and ownership concepts while applying Floyd's algorithm.

6

Advanced

Finding Cycle Start Node

🤔Before reading on: after detecting a cycle, do you think the meeting point is the cycle start? Commit to your answer.

Concept: After detecting a cycle, reset one pointer to head and move both one step at a time to find cycle start.

Once slow and fast meet inside the cycle, move slow to head. Then move slow and fast one step each until they meet again. This meeting point is the cycle start node.

Result

You can identify the exact node where the cycle begins.

Knowing how to find the cycle start helps in cycle removal and deeper linked list manipulation.

7

Expert

Why Floyd's Algorithm is Space Efficient

🤔Before reading on: do you think Floyd's algorithm uses extra memory proportional to list size? Commit to your answer.

Concept: Floyd's algorithm uses only two pointers, no extra data structures, making it O(1) space.

Unlike hash-based methods that store visited nodes, Floyd's algorithm only tracks two pointers. This saves memory and improves performance on large lists.

Result

Cycle detection is done in constant space and linear time.

Understanding space efficiency explains why Floyd's algorithm is preferred in memory-sensitive environments.

Under the Hood

Floyd's algorithm works because the fast pointer moves twice as fast as the slow pointer. If a cycle exists, the fast pointer laps the slow pointer inside the loop. The meeting point occurs because the distance between pointers decreases by one each step inside the cycle until they meet.

Why designed this way?

The algorithm was designed to detect cycles without extra memory, unlike hash tables. It uses pointer speed difference to guarantee detection. Alternatives like marking nodes or storing visited nodes require extra space, which is costly for large lists.

Start:
Head -> [Node1] -> [Node2] -> [Node3] -> [Node4] -> [Node5]
                                   ↑                 ↓
                                   ←-----------------

Pointers:
Slow: moves 1 step
Fast: moves 2 steps

Inside cycle:
Distance between pointers shrinks by 1 each iteration
Eventually, Slow == Fast -> cycle detected

Myth Busters - 3 Common Misconceptions

Quick: do you think Floyd's algorithm can detect cycles in a singly linked list without any pointers moving at different speeds? Commit yes or no.

Common Belief: Some believe a single pointer moving through the list can detect cycles by itself.

Reality: A single pointer cannot detect cycles because it will loop infinitely without knowing it has visited nodes before.

Why it matters: Relying on one pointer causes infinite loops and program hangs when cycles exist.

Quick: do you think the meeting point of slow and fast pointers is always the start of the cycle? Commit yes or no.

Common Belief: Many think the first meeting point is the cycle's start node.

Reality: The meeting point is inside the cycle but not necessarily the start. Additional steps are needed to find the cycle start.

Why it matters: Mistaking meeting point for cycle start leads to incorrect cycle removal or analysis.

Quick: do you think Floyd's algorithm requires extra memory proportional to the list size? Commit yes or no.

Common Belief: Some assume cycle detection needs extra memory like hash sets.

Reality: Floyd's algorithm uses only two pointers and constant extra space.

Why it matters: Misunderstanding space usage may lead to inefficient solutions or unnecessary complexity.

Expert Zone

1

The distance between slow and fast pointers inside the cycle decreases by exactly one node per iteration, guaranteeing eventual meeting.

2

Resetting one pointer to head after detection and moving both pointers at the same speed exploits the mathematical relationship between cycle length and list length.

3

Floyd's algorithm can be adapted to detect cycles in other structures like graphs or arrays with pointer-like indices.

When NOT to use

Avoid Floyd's algorithm if you need to know all nodes in the cycle or count cycle length directly; use hash-based detection or cycle length algorithms instead.

Production Patterns

Used in garbage collectors to detect reference cycles, in network routing to detect loops, and in interview coding tests as a standard cycle detection method.

Connections

Tortoise and Hare Algorithm

Floyd's algorithm is also called the Tortoise and Hare algorithm; they are the same concept.

Knowing the alternative name helps recognize the algorithm in different contexts and literature.

Cycle Detection in Graphs

Floyd's algorithm is a specialized cycle detection for linked lists, while graphs require more general algorithms like DFS.

Understanding Floyd's algorithm clarifies why cycle detection in graphs is more complex and needs different approaches.

Race Conditions in Operating Systems

Both involve processes moving at different speeds and meeting conditions that cause conflicts or detection.

Recognizing speed differences and meeting points in Floyd's algorithm helps understand timing issues in concurrent systems.

Common Pitfalls

#1 Moving fast pointer only one step instead of two.

Wrong approach:

while let (Some(slow_next), Some(fast_next)) = (slow.next.as_ref(), fast.next.as_ref()) {
slow = slow_next;
fast = fast_next; // moves only one step
if slow == fast {
return true;
}
}

Correct approach:

while let (Some(slow_next), Some(fast_next)) = (slow.next.as_ref(), fast.next.as_ref().and_then(|n| n.next.as_ref())) {
slow = slow_next;
fast = fast_next; // moves two steps
if slow == fast {
return true;
}
}

Root cause:

Confusing pointer movement speed breaks the algorithm's logic and fails to detect cycles.

#2 Not checking if fast or fast.next is None before moving fast pointer.

Wrong approach:

fast = fast.next.unwrap().next.unwrap(); // unwrap without checking

Correct approach:

if let Some(next1) = fast.next.as_ref() {
if let Some(next2) = next1.next.as_ref() {
fast = next2;
} else {
return false;
}
} else {
return false;
}

Root cause:

Ignoring null checks causes runtime panics or crashes.

#3 Assuming meeting point is cycle start and returning it directly.

Wrong approach:

if slow == fast {
return Some(slow);
}

Correct approach:

if slow == fast {
slow = head;
while slow != fast {
slow = slow.next.as_ref().unwrap();
fast = fast.next.as_ref().unwrap();
}
return Some(slow);
}

Root cause:

Misunderstanding the algorithm's cycle start detection step leads to incorrect results.

Key Takeaways

Floyd's algorithm detects cycles by using two pointers moving at different speeds through a linked list.

If a cycle exists, the faster pointer will eventually meet the slower pointer inside the loop.

The meeting point is inside the cycle but not necessarily the start; additional steps find the cycle start node.

This algorithm uses constant extra space, making it efficient for large lists.

Proper pointer movement and null checks are critical to avoid errors and crashes.

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