Detect Cycle in Linked List Floyd's Algorithm in DSA C++

Mental Model

Use two pointers moving at different speeds to find if a loop exists in a linked list.

Analogy: Imagine two runners on a circular track: one runs slowly, the other runs fast. If the track is a loop, the fast runner will eventually catch the slow runner.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑
fast ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5 with a cycle from 5 back to 3

Goal: Detect if the linked list has a cycle using Floyd's algorithm

Step 1: Initialize slow and fast pointers at head (node 1)

1 -> 2 -> 3 -> 4 -> 5 ->
          ↑slow, ↑fast (both at 1)

Why: Start both pointers at the beginning to begin traversal

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

1 -> 2 -> 3 -> 4 -> 5 ->
               ↑fast
          ↑slow

Why: Advance pointers at different speeds to detect cycle

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

1 -> 2 -> 3 -> 4 -> 5 ->
                    ↑fast
               ↑slow

Why: Continue advancing pointers; fast moves twice as fast

Step 4: Move slow by 1 step to node 4, fast moves 2 steps: from 5 -> 3 -> 4 (cycle)

1 -> 2 -> 3 -> 4 -> 5 ->
                    ↑slow, ↑fast

Why: Fast pointer loops back due to cycle; pointers meet at node 4

Step 5: slow == fast, cycle detected

Pointers meet at node 4 confirming cycle

Why: When fast catches up to slow, a cycle exists

Result:

Cycle detected: slow and fast pointers meet at node 4

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

bool detectCycle(Node* head) {
    if (!head) return false; // empty list has no cycle
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next; // move slow by 1
        fast = fast->next->next; // move fast by 2
        if (slow == fast) {
            return true; // cycle detected
        }
    }
    return false; // no cycle
}

int main() {
    // Create nodes
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    // Create cycle: 5 -> 3
    head->next->next->next->next->next = head->next->next;

    bool hasCycle = detectCycle(head);
    cout << (hasCycle ? "Cycle detected" : "No cycle") << endl;
    return 0;
}

if (!head) return false; // empty list has no cycle

handle empty list edge case

Node* slow = head; Node* fast = head;

initialize slow and fast pointers at head

while (fast && fast->next) {

loop while fast pointer and its next exist to avoid null access

slow = slow->next; // move slow by 1

advance slow pointer by one node

fast = fast->next->next; // move fast by 2

advance fast pointer by two nodes

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

if pointers meet, cycle exists

return false;

no cycle found after traversal

Output

Cycle detected

Complexity Analysis

Time: O(n) because each pointer traverses nodes at most once until they meet or reach the end

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), Floyd's algorithm uses constant space making it more efficient

Edge Cases

empty list

returns false immediately since no nodes exist

DSA C++

if (!head) return false; // empty list has no cycle

single node without cycle

returns false as next is null

DSA C++

while (fast && fast->next)

single node with cycle to itself

detects cycle as slow and fast meet immediately

DSA C++

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

When to Use This Pattern

When you need to detect a cycle in a linked list efficiently, use Floyd's cycle detection because it uses two pointers moving at different speeds to find loops without extra memory.

Common Mistakes

Mistake: Not checking if fast or fast->next is null before advancing fast pointer
Fix: Add condition 'while (fast && fast->next)' to avoid null pointer dereference

Mistake: Moving slow and fast pointers incorrectly (e.g., both by one step)
Fix: Move slow by one step and fast by two steps to ensure detection

Summary

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

Use when you want to find loops in linked lists without extra memory.

The fast pointer will catch the slow pointer if a cycle exists, like runners on a circular track.

Practice

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

easy

A. To find the middle element of the linked list

B. To sort the linked list in ascending order

C. To reverse the linked list

D. To detect if there is a cycle (loop) in the linked list

Solution

1. Step 1: Understand Floyd's Algorithm goal

   Floyd's Cycle Detection Algorithm is designed to check if a linked list contains a cycle, meaning a node points back to a previous node.

2. Step 2: Compare with other linked list operations

   Sorting, reversing, or finding the middle element are different operations and not the purpose of this algorithm.

3. Final Answer:

   To detect if there is a cycle (loop) in the linked list -> Option D

4. Quick Check:

   Cycle detection = Detect cycle [OK]

Hint: Floyd's algorithm finds loops, not sorting or reversing [OK]

Common Mistakes:

• Confusing cycle detection with sorting
• Thinking it finds the middle node
• Assuming it reverses the list

2. Which of the following correctly initializes the two pointers used in Floyd's Cycle Detection Algorithm in C++?

easy

A. ListNode* slow = head; ListNode* fast = head;

B. ListNode* slow = head->next; ListNode* fast = head;

C. ListNode* slow = nullptr; ListNode* fast = head;

D. ListNode* slow = head; ListNode* fast = head->next;

Solution

1. Step 1: Understand pointer initialization in Floyd's algorithm

   Both slow and fast pointers start at the head node to begin traversal.

2. Step 2: Check each option

   ListNode* slow = head; ListNode* fast = head; initializes both pointers at head, which is the standard approach. Other options start pointers differently, which can cause errors or miss cycles.

3. Final Answer:

   ListNode* slow = head; ListNode* fast = head; -> Option A

4. Quick Check:

   Both pointers start at head [OK]

Hint: Start both pointers at head for Floyd's algorithm [OK]

Common Mistakes:

• Starting fast pointer at head->next causes skipping
• Initializing slow as nullptr causes null errors
• Swapping slow and fast initialization

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

#include <iostream>

struct Node {
  int data;
  Node* next;
};

bool hasCycle(Node* head) {
  Node* slow = head;
  Node* fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;
  }
  return false;
}

int main() {
  Node a{1, nullptr};
  Node b{2, nullptr};
  Node c{3, nullptr};
  a.next = &b;
  b.next = &c;
  c.next = &b; // cycle here
  bool result = hasCycle(&a);
  std::cout << (result ? "Cycle detected" : "No cycle") << std::endl;
  return 0;
}

medium

A. No cycle

B. Cycle detected

C. Compilation error

D. Runtime error

Solution

1. Step 1: Analyze linked list structure

   Nodes a, b, c are linked as a->b->c, and c points back to b, creating a cycle.

2. Step 2: Trace Floyd's algorithm behavior

   Slow and fast pointers will eventually meet inside the cycle, so hasCycle returns true.

3. Final Answer:

   Cycle detected -> Option B

4. Quick Check:

   Cycle exists, so output is "Cycle detected" [OK]

Hint: If a node points back, Floyd detects cycle [OK]

Common Mistakes:

• Ignoring the cycle created by c.next = &b
• Assuming no cycle because list looks linear
• Confusing output with compilation or runtime errors

4. Identify the bug in this Floyd's Cycle Detection code snippet:

bool detectCycle(Node* head) {
  Node* slow = head;
  Node* fast = head;
  while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;
  }
  return false;
}

medium

A. The return type should be void, not bool

B. Pointers slow and fast should start at different nodes

C. The while condition should check if fast is not nullptr before fast->next

D. The comparison if (slow == fast) should be outside the loop

Solution

1. Step 1: Check while loop condition safety

   The code checks fast->next and fast->next->next but does not check if fast itself is nullptr, risking null pointer access.

2. Step 2: Correct condition order

   Proper check is to ensure fast is not nullptr before accessing fast->next to avoid runtime errors.

3. Final Answer:

   The while condition should check if fast is not nullptr before fast->next -> Option C

4. Quick Check:

   Check fast != nullptr before fast->next [OK]

Hint: Always check pointer not null before accessing members [OK]

Common Mistakes:

• Skipping null check on fast pointer
• Starting pointers at different nodes unnecessarily
• Moving comparison outside loop causing infinite loop

5. Given a linked list where a cycle exists, how can Floyd's algorithm be extended to find the exact node where the cycle begins?

hard

A. After detecting the cycle, reset one pointer to head and move both pointers one step at a time until they meet at the cycle start.

B. Count the number of nodes in the list and divide by two to find the cycle start.

C. Use a hash set to store visited nodes and find the first repeated node.

D. Reverse the linked list and check where the reversal breaks to find the cycle start.

Solution

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

   First, detect the cycle by moving slow and fast pointers until they meet inside the cycle.

2. Step 2: Find cycle start node

   Reset one pointer to head, then move both pointers one step at a time; their meeting point is the cycle start node.

3. Final Answer:

   After detecting the cycle, reset one pointer to head and move both pointers one step at a time until they meet at the cycle start. -> Option A

4. Quick Check:

   Reset pointer + move stepwise = cycle start [OK]

Hint: Reset pointer to head after detection, move both stepwise [OK]

Common Mistakes:

• Trying to find cycle start by counting nodes
• Using extra memory like hash sets (not Floyd's method)
• Reversing list which breaks structure