Detect Cycle in Linked List Floyd's Algorithm in DSA C++ - 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 find this loop without extra memory. If the fast pointer meets the slow pointer, a cycle exists. This method is efficient and simple to implement.

Why it matters

Without detecting cycles, programs can get stuck in endless loops when processing linked lists, causing crashes or freezes. Detecting cycles helps avoid these problems and ensures data structures behave correctly. It is crucial in many applications like network routing, memory management, and detecting infinite loops in data.

Where it fits

Before learning this, you should understand what a linked list is and how pointers work. After this, you can learn about removing cycles, finding the start of the cycle, and other linked list algorithms like reversing or merging lists.

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 slowly, the other runs faster. If the track loops, the faster runner will eventually catch up to the slower one.

Linked List with cycle:

Head -> 1 -> 2 -> 3 -> 4 -> 5
               ^              |
               |--------------|

Pointers:
Slow moves one step at a time
Fast moves two steps at a time
If fast meets slow, cycle detected

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 sequence of connected boxes ending with null.

Understanding the structure of linked lists is essential before detecting cycles because the algorithm depends on pointer navigation.

2

Foundation

What is a Cycle in Linked List

Concept: A cycle means the list loops back to an earlier node instead of ending.

In a cycle, a node's next pointer points to a previous node, creating a loop. This means traversing the list can go on forever without reaching null.

Result

The list no longer has a clear end, causing infinite traversal if unchecked.

Recognizing what a cycle looks like helps understand why normal traversal fails and why special detection is needed.

3

Intermediate

Introducing Two Pointers Technique

🤔Before reading on: do you think the fast pointer can skip over the slow pointer without meeting it? Commit to yes or no.

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

We use a slow pointer that moves one step at a time and a fast pointer that moves two steps. If the list has no cycle, fast reaches null. If there is a cycle, fast will eventually catch slow inside the loop.

Result

If pointers meet, cycle exists; if fast reaches null, no cycle.

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

4

Intermediate

Implementing Floyd's Cycle Detection Algorithm

Concept: Write code to move pointers and check for cycle presence.

Initialize slow and fast pointers at head. Move slow by one node and fast by two nodes in a loop. If fast or fast->next is null, return false (no cycle). If slow equals fast, return true (cycle detected).

Result

The function returns true if a cycle is found, false otherwise.

This step shows how the theory translates into a simple, efficient algorithm.

5

Intermediate

Dry Run Example of Floyd's Algorithm

Concept: Walk through the algorithm step-by-step on a sample list with a cycle.

List: 1 -> 2 -> 3 -> 4 -> 5 -> back to 3 Start: slow=1, fast=1 Step 1: slow=2, fast=3 Step 2: slow=3, fast=5 Step 3: slow=4, fast=4 (fast caught slow) Cycle detected.

Result

Pointers meet at node 4 confirming the cycle.

Seeing the pointers meet in action builds intuition about why the algorithm works.

6

Advanced

Finding Cycle Start Node

🤔Before reading on: do you think the meeting point of pointers is always the cycle start? Commit yes or no.

Concept: After detecting a cycle, find the exact node where the cycle begins.

Once slow and fast meet, reset slow to head. Move both pointers one step at a time. The node where they meet again is the cycle start.

Result

You can identify the node where the cycle begins.

Knowing how to find the cycle start helps in fixing or analyzing cycles in linked lists.

7

Expert

Why Floyd's Algorithm is Optimal

🤔Quick: do you think using extra memory like hash sets is better than Floyd's algorithm? Commit yes or no.

Concept: Floyd's algorithm uses constant memory and linear time, making it optimal for cycle detection.

Other methods use extra space to remember visited nodes. Floyd's uses two pointers only, saving memory. It runs in O(n) time and O(1) space, which is the best possible for this problem.

Result

Floyd's algorithm is the most efficient known method for cycle detection in linked lists.

Understanding the efficiency tradeoffs explains why Floyd's algorithm is preferred in real systems.

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. This is similar to two runners on a track where the faster one eventually catches the slower one. The pointers' meeting point proves a cycle.

Why designed this way?

The algorithm was designed to detect cycles without extra memory, unlike hash-based methods. It balances simplicity and efficiency, avoiding the overhead of storing visited nodes. Alternatives like marking nodes or using extra data structures were rejected due to higher space costs.

Start
  ↓
[Head]
  ↓
Slow -> moves 1 step
Fast -> moves 2 steps

Cycle exists?
  ↓ Yes
Pointers meet inside cycle
  ↓ No
Fast reaches null

Result: Cycle detected if pointers meet

Myth Busters - 3 Common Misconceptions

Quick: Do you think the fast pointer can miss the slow pointer if it jumps over it? Commit yes or no.

Common Belief: The fast pointer might skip the slow pointer and never meet, missing the cycle.

Reality: Because the fast pointer moves two steps and the slow pointer one, they will always meet inside a cycle eventually.

Why it matters: Believing this causes unnecessary complexity or wrong algorithms, wasting time and resources.

Quick: Do you think the meeting point of pointers is always the start of the cycle? Commit yes or no.

Common Belief: The node where slow and fast meet is the cycle's starting node.

Reality: The meeting point can be anywhere inside the cycle, not necessarily the start.

Why it matters: Assuming this leads to incorrect cycle start detection and bugs in fixing cycles.

Quick: Do you think Floyd's algorithm uses extra memory to detect cycles? Commit yes or no.

Common Belief: Cycle detection requires extra memory like hash sets to track visited nodes.

Reality: Floyd's algorithm uses only two pointers and constant memory, no extra storage needed.

Why it matters: Misunderstanding this leads to inefficient solutions and missed opportunities for optimization.

Expert Zone

1

The distance between the head and cycle start equals the distance from meeting point to cycle start when pointers move at same speed after meeting.

2

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

3

In some cases, modifying the list temporarily can help detect cycles faster but risks corrupting data if not restored.

When NOT to use

If you need to know all nodes in the cycle or count cycle length efficiently, other algorithms or data structures like hash sets may be better. Also, if the list is immutable or pointers are not accessible, Floyd's algorithm cannot be applied.

Production Patterns

Used in garbage collectors to detect reference cycles, in network routing to detect loops, and in debugging tools to find infinite loops in linked data structures.

Connections

Tortoise and Hare Algorithm

Floyd's algorithm is also known as the Tortoise and Hare algorithm, sharing the same two-pointer speed concept.

Knowing this helps recognize the algorithm under different names and contexts.

Cycle Detection in Graphs

Floyd's algorithm is a specialized cycle detection for linked lists, while graph cycle detection uses DFS or Union-Find.

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

Race Conditions in Operating Systems

Both involve processes moving at different speeds and the possibility of meeting or conflicting states.

Recognizing similar patterns in OS helps understand synchronization and deadlock detection.

Common Pitfalls

#1 Not checking if fast or fast->next is null before moving pointers.

Wrong approach:

while (fast != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;

Correct approach:

while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;

Root cause:

Assuming fast->next always exists leads to null pointer dereference and crashes.

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

Wrong approach:

if (slow == fast) return slow; // cycle start assumed

Correct approach:

if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // actual cycle start
}

Root cause:

Confusing meeting point with cycle start causes incorrect cycle start identification.

#3 Using extra memory like hash sets unnecessarily.

Wrong approach:

std::unordered_set visited;
while (head != nullptr) {
if (visited.count(head)) return true;
visited.insert(head);
head = head->next;
}
return false;

Correct approach:

Use Floyd's algorithm with two pointers to detect cycle without extra memory.

Root cause:

Not knowing Floyd's algorithm leads to inefficient solutions with higher memory use.

Key Takeaways

Detecting cycles in linked lists prevents infinite loops and program crashes.

Floyd's algorithm uses two pointers moving at different speeds to detect cycles efficiently.

If the fast pointer meets the slow pointer, a cycle exists; if fast reaches null, no cycle.

After detection, resetting one pointer to head and moving both one step finds the cycle start.

Floyd's algorithm is optimal with O(n) time and O(1) space, making it the preferred method.

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