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 with a null. Floyd's Algorithm, also called the Tortoise and Hare algorithm, uses two pointers moving at different speeds to find this loop. If the fast pointer catches up to the slow pointer, a cycle exists. This method is efficient and uses no extra memory.

Why it matters

Without detecting cycles, programs can get stuck in infinite loops when processing linked lists, causing crashes or freezes. Detecting cycles helps ensure data structures behave correctly and safely. It is essential 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, detecting cycles in other data structures like graphs, or advanced linked list operations.

Mental Model

Core Idea

If two pointers move through a linked list at different speeds, they will meet if there is a cycle.

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:

Start -> [Node1] -> [Node2] -> [Node3] -> [Node4] ->
                      ^                             |
                      |-----------------------------|

Pointers:
Slow (Tortoise) moves one step at a time.
Fast (Hare) moves two steps at a time.
If Fast meets Slow, 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 holds data and a pointer to the next node. The last node points to null, meaning the list ends there. Example: Node1 -> Node2 -> Node3 -> null Each arrow is a pointer to the next node.

Result

You can visualize a linked list as a chain of connected boxes ending with null.

Understanding the structure of linked lists is essential before detecting cycles because cycles break the normal end condition.

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. Example: Node1 -> Node2 -> Node3 -> Node4 ^ | |--------------| Here, Node4 points back to Node2, forming a cycle.

Result

Traversal without cycle detection will never reach null and loop infinitely.

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

3

Intermediate

Two Pointer Technique Introduction

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

We use a slow pointer that moves one node at a time and a fast pointer that moves two nodes at a time. If there is no cycle, the fast pointer will reach null. If there is a cycle, the fast pointer will eventually catch the slow pointer.

Result

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

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

4

Intermediate

Implementing Floyd's Cycle Detection in C#

🤔Before reading on: do you think the fast pointer moves one or two steps each time? Commit to your answer.

Concept: Implement the algorithm using two pointers in C# to detect cycles.

class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } bool HasCycle(Node head) { Node slow = head; Node fast = head; while (fast != null && fast.next != null) { 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 }

Result

Returns true if cycle exists, false otherwise.

Knowing how to implement the two-pointer technique is key to practical cycle detection.

5

Intermediate

Dry Run of Floyd's Algorithm

🤔Before reading on: do you think slow and fast pointers meet at the start of the cycle or somewhere else? Commit to your answer.

Concept: Step through the algorithm to see how pointers move and meet.

Example list with cycle: Node1 -> Node2 -> Node3 -> Node4 -> Node5 ^ | |-----------------------| Steps: - Start: slow=Node1, fast=Node1 - Move1: slow=Node2, fast=Node3 - Move2: slow=Node3, fast=Node5 - Move3: slow=Node4, fast=Node3 - Move4: slow=Node5, fast=Node5 (meet) Pointers meet at Node5, cycle detected.

Result

Pointers meet inside the cycle, confirming its presence.

Seeing the pointers meet inside the cycle clarifies why the algorithm works.

6

Advanced

Finding Cycle Start Node

🤔Before reading on: do you think the meeting point is always the start of the cycle? Commit to your answer.

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. Code snippet: Node FindCycleStart(Node head) { Node slow = head, fast = head; do { slow = slow.next; fast = fast.next.next; } while (slow != fast); slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; }

Result

Returns the node where the cycle begins.

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

7

Expert

Algorithm Limitations and Edge Cases

🤔Before reading on: do you think Floyd's algorithm works on empty or single-node lists? Commit to your answer.

Concept: Understand when the algorithm might fail or behave unexpectedly and how to handle those cases.

Edge cases: - Empty list (head is null): no cycle. - Single node with no cycle: no cycle. - Single node pointing to itself: cycle. The algorithm handles these by checking fast and fast.next for null before moving. Limitations: - Cannot detect cycle length directly. - Does not remove cycle, only detects. - Assumes singly linked list structure.

Result

Algorithm safely returns false for no cycle and true for cycle in all cases.

Understanding edge cases prevents bugs and ensures robust code.

Under the Hood

Floyd's algorithm uses two pointers moving at different speeds through the linked list nodes. If a cycle exists, the fast pointer laps the slow pointer inside the loop because it moves twice as fast. The meeting point proves a cycle. Resetting one pointer to the head and moving both at the same speed finds the cycle start because the distance from head to cycle start equals the distance from meeting point to cycle start inside the loop.

Why designed this way?

This method was designed to detect cycles efficiently without extra memory like hash sets. It uses pointer speed difference to detect loops, a clever tradeoff between time and space. Alternatives like storing visited nodes use more memory, so Floyd's algorithm is preferred for memory-constrained environments.

Start
  │
  ▼
[Head] -> [Node1] -> [Node2] -> [Node3] -> [Node4]
                      ↑                      │
                      └──────────────────────┘

Pointers:
Slow: moves one step ->
Fast: moves two steps ⇒

If cycle:
Fast eventually meets Slow inside loop.

Then:
Reset Slow to Head.
Move both one step at a time.
They meet at cycle start node.

Myth Busters - 4 Common Misconceptions

Quick: Does Floyd's algorithm detect the length of the cycle? Commit yes or no.

Common Belief: Floyd's algorithm tells you the length of the cycle directly.

Reality: Floyd's algorithm only detects if a cycle exists and can find the start node, but it does not directly give the cycle length.

Why it matters: Assuming it gives cycle length can lead to wrong conclusions or extra code to calculate length separately.

Quick: Can the fast pointer skip over the slow pointer without meeting? Commit yes or no.

Common Belief: The fast pointer might jump over the slow pointer and miss the cycle.

Reality: Because the fast pointer moves two steps and slow moves one, they cannot skip each other without meeting if a cycle exists.

Why it matters: This ensures the algorithm is reliable and won't miss cycles due to pointer speed differences.

Quick: Does the algorithm work on doubly linked lists the same way? Commit yes or no.

Common Belief: Floyd's algorithm works the same on doubly linked lists.

Reality: While it can detect cycles in doubly linked lists, the algorithm is designed for singly linked lists and may need adjustments for others.

Why it matters: Misapplying it without understanding can cause incorrect results or inefficiencies.

Quick: Does the meeting point of pointers always indicate the cycle start? Commit yes or no.

Common Belief: The point where slow and fast pointers meet is always the start of the cycle.

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: Confusing meeting point with cycle start can cause errors in cycle removal or analysis.

Expert Zone

1

The distance from head to cycle start equals the distance from meeting point to cycle start inside the loop, enabling cycle start detection.

2

Floyd's algorithm can be extended to find cycle length by counting nodes after meeting point until pointers meet again.

3

In concurrent or multi-threaded environments, pointer movement assumptions may break, requiring synchronization.

When NOT to use

Avoid Floyd's algorithm when you need to detect cycles in complex graph structures or when you require cycle length immediately. Use hash-based detection or graph traversal algorithms like DFS for those cases.

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

Cycle Detection in Graphs

Builds-on

Understanding cycle detection in linked lists helps grasp more complex cycle detection in graphs, which use similar principles but require different algorithms.

Two-pointer Technique

Same pattern

Floyd's algorithm is a classic example of the two-pointer technique, which is widely used in array and string problems to optimize time and space.

Race Conditions in Operating Systems

Conceptual similarity

The idea of two processes moving at different speeds and meeting unexpectedly relates to race conditions, helping understand synchronization issues.

Common Pitfalls

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

Wrong approach:

while (fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}

Correct approach:

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}

Root cause:

Assuming fast and fast.next are always valid causes null reference errors.

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

Wrong approach:

if (slow == fast) return slow; // wrong: meeting point not cycle start

Correct approach:

slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // correct cycle start

Root cause:

Confusing the meeting point inside the cycle with the actual cycle start node.

#3 Using Floyd's algorithm on empty or single-node lists without checks.

Wrong approach:

Node slow = head;
Node fast = head.next.next; // causes null reference if list too short

Correct approach:

Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) { ... }

Root cause:

Not handling edge cases leads to runtime errors.

Key Takeaways

Floyd's algorithm detects cycles in linked lists by using two pointers moving at different speeds.

If the fast pointer meets the slow pointer, a cycle exists; otherwise, the list ends normally.

After detecting a cycle, resetting one pointer to head and moving both one step at a time finds the cycle start node.

Proper null checks prevent runtime errors, especially in empty or short lists.

Understanding this algorithm helps prevent infinite loops and is widely used in real-world systems.

Practice

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

easy

A. To reverse the linked list

B. To check if the linked list contains a cycle

C. To sort the linked list

D. To find the middle element of the linked list

Solution

1. Step 1: Understand Floyd's Algorithm goal

   Floyd's Cycle Detection Algorithm is designed to detect if a linked list has a cycle by using two pointers moving at different speeds.

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 check if the linked list contains a cycle -> Option B

4. Quick Check:

   Cycle detection = Check for cycle [OK]

Hint: Floyd's algorithm uses two pointers to find cycles [OK]

Common Mistakes:

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

2. Which of the following is the correct way to initialize the two pointers used in Floyd's Cycle Detection Algorithm in C#?

easy

A. Node slow = head; Node fast = head;

B. Node slow = null; Node fast = head;

C. Node slow = head; Node fast = head.next;

D. Node slow = head.next; Node fast = head.next.next;

Solution

1. Step 1: Understand pointer initialization

   Slow pointer starts at head, fast pointer starts at head.next to ensure fast moves ahead and cycle detection works correctly.

2. Step 2: Check other options for correctness

   Initializing both pointers at head can cause immediate equality and false positive; starting slow as null or fast too far ahead risks null reference.

3. Final Answer:

   Node slow = head; Node fast = head.next; -> Option C

4. Quick Check:

   Slow at head, fast at head.next [OK]

Hint: Start slow at head and fast at head.next for correct cycle detection [OK]

Common Mistakes:

• Starting both pointers at head causing false positives
• Starting slow pointer as null
• Skipping initialization of one pointer

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

class Node {
  public int val;
  public Node next;
  public Node(int v) { val = v; next = null; }
}

Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = head.next; // cycle here

bool HasCycle(Node head) {
  Node slow = head, fast = head;
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
  }
  return false;
}

Console.WriteLine(HasCycle(head));

medium

A. Runtime Exception

B. False

C. Compilation Error

D. True

Solution

1. Step 1: Analyze linked list structure

   The list has nodes 1 -> 2 -> 3, and then 3 points back to 2, creating a cycle.

2. Step 2: Trace Floyd's algorithm execution

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

3. Final Answer:

   True -> Option D

4. Quick Check:

   Cycle present = true [OK]

Hint: Cycle means slow and fast pointers meet [OK]

Common Mistakes:

• Ignoring the cycle created by linking back
• Assuming no cycle returns true
• Confusing syntax errors with logic

4. Identify the bug in the following C# code for detecting a cycle using Floyd's algorithm:

bool HasCycle(Node head) {
  Node slow = head.next;
  Node fast = head.next.next;
  while (fast != null && fast.next != null) {
    if (slow == fast) return true;
    slow = slow.next;
    fast = fast.next.next;
  }
  return false;
}

medium

A. Pointers initialized incorrectly causing null reference

B. Missing check for slow pointer being null

C. Loop condition should use OR instead of AND

D. No bug, code works fine

Solution

1. Step 1: Check pointer initialization

   Initializing slow as head.next and fast as head.next.next can cause null reference if list is too short.

2. Step 2: Understand safe initialization

   Both pointers should start at head to avoid null errors and correctly detect cycles.

3. Final Answer:

   Pointers initialized incorrectly causing null reference -> Option A

4. Quick Check:

   Incorrect pointer start = null error risk [OK]

Hint: Start both pointers at head to avoid null errors [OK]

Common Mistakes:

• Starting pointers too far ahead
• Not checking for null before accessing next
• Using wrong loop condition operators

5. Given a linked list where the last node points back to the head, how can Floyd's Cycle Detection Algorithm be modified to find the exact node where the cycle begins?

hard

A. After detecting cycle, reset one pointer to head and move both one step until they meet

B. Use a hash set to store visited nodes instead of pointers

C. Count nodes until slow and fast pointers meet and return count

D. Reverse the linked list and check for null pointers

Solution

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

   First, detect if a cycle exists by moving slow and fast pointers until they meet.

2. Step 2: Find cycle start node

   Reset one pointer to head, then move both pointers one step at a time; the node where they meet is the cycle start.

3. Final Answer:

   After detecting cycle, reset one pointer to head and move both one step until they meet -> Option A

4. Quick Check:

   Reset pointer + move one step = cycle start [OK]

Hint: Reset pointer to head after cycle detection to find start [OK]

Common Mistakes:

• Using hash sets instead of Floyd's algorithm
• Counting nodes without resetting pointers
• Reversing list which breaks cycle detection