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

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

Start: slow = head, fast = head

↓

Check: fast != null and fast->next != null?

No→No cycle found, return false

Yes↓

Move slow by 1 step

↓

Move fast by 2 steps

↓

Check: slow == fast?

No→Repeat loop

Yes↓

Cycle detected, return true

The algorithm uses two pointers moving at different speeds to detect if a cycle exists by checking if they meet.

Execution Sample

DSA C++

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

This code moves two pointers through the list to find if they meet, indicating a cycle.

Execution Table

Step	Operation	slow Pointer	fast Pointer	Cycle Detected?	Visual State
1	Initialize pointers	head (Node 10)	head (Node 10)	No	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:──┼ └────────┘ └────────┘ └────────┘ └────────┘ slow, fast → head
2	Move slow by 1 step, fast by 2 steps	Node 20	Node 30	No	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:──┼ └────────┘ └────────┘ └────────┘ └────────┘ slow → Node 20 fast → Node 30
3	Move slow by 1 step, fast by 2 steps	Node 30	Node 20	No	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:──┼ └────────┘ └────────┘ └────────┘ └────────┘ slow → Node 30 fast → Node 20
4	Move slow by 1 step, fast by 2 steps	Node 40	Node 40	Yes	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:──┼ └────────┘ └────────┘ └────────┘ └────────┘ slow → Node 40 fast → Node 40 Pointers meet, cycle detected

💡 Pointers slow and fast meet at Node 40, cycle detected, return true

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4
slow	Node 10	Node 20	Node 30	Node 40
fast	Node 10	Node 30	Node 20	Node 40

Key Moments - 3 Insights

Why do we move fast pointer by two steps and slow pointer by one step?

Moving fast pointer twice as fast ensures that if a cycle exists, fast will eventually catch up to slow inside the loop, as shown in steps 2-4 of the execution_table.

What happens if the list has no cycle?

The fast pointer will reach the end (null) first, causing the loop to exit without slow and fast meeting, as indicated by the exit condition in the concept_flow.

Why do we check both fast and fast->next in the loop condition?

Checking fast and fast->next prevents accessing null pointers when moving fast two steps ahead, avoiding runtime errors, as shown in the concept_flow decision step.

Visual Quiz - 3 Questions

Look at the execution_table, what node is the slow pointer at after Step 3?

A Node 30

B Node 20

C Node 40

D Node 10

💡 Hint

Check the 'slow Pointer' column in row for Step 3 in execution_table

At which step do slow and fast pointers meet indicating a cycle?

A Step 3

B Step 4

C Step 2

D Step 1

💡 Hint

Look at the 'Cycle Detected?' column in execution_table rows

If the fast pointer moved only one step each time instead of two, what would happen?

A Fast pointer would reach null faster

B Cycle detection would fail because pointers never meet

C Cycle detection would still work but slower

D Slow pointer would move faster than fast pointer

💡 Hint

Consider how pointer speeds affect meeting inside a cycle, related to key_moments explanation

Concept Snapshot

Detect Cycle in Linked List using Floyd's Algorithm:
- Use two pointers: slow (1 step), fast (2 steps)
- Move pointers until fast or fast->next is null (no cycle)
- If slow == fast at any point, cycle exists
- Returns true if cycle found, else false

Full Transcript

This concept shows how to detect a cycle in a linked list using Floyd's algorithm. Two pointers start at the head. The slow pointer moves one node at a time, the fast pointer moves two nodes at a time. If the list has a cycle, the fast pointer will eventually catch up to the slow pointer inside the loop. If the fast pointer reaches the end (null), no cycle exists. The execution table traces each step showing pointer positions and the linked list state. Key moments clarify why pointers move at different speeds and why we check for null pointers. The visual quiz tests understanding of pointer positions and cycle detection steps.

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