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

↓

Move slow by 1 step

↓

Move fast by 2 steps

↓

Check if slow == fast?

No→Check if fast or fast.next is null?

↓

Cycle detected

Two pointers move through the list at different speeds. If they meet, a cycle exists. If fast pointer reaches end, no cycle.

Execution Sample

DSA C#

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

Moves slow pointer by one and fast pointer by two steps to detect cycle in linked list.

Execution Table

Step	Operation	slow Pointer Node	fast Pointer Node	Pointer Changes	Visual State
1	Initialize pointers	Node 1	Node 1	slow=head, fast=head	┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │ │ data:2 │ │ data:3 │ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head slow, fast → Node 1
2	Move slow by 1 step	Node 2	Node 3	slow=slow.next, fast=fast.next.next	┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │ │ data:2 │ │ data:3 │ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head slow → Node 2 fast → Node 3
3	Check slow == fast?	Node 2	Node 3	No match	No cycle detected yet, continue
4	Move slow by 1 step	Node 3	null	slow=slow.next, fast=fast.next.next (fast.next is null)	┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │ │ data:2 │ │ data:3 │ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head slow → Node 3 fast → null (end)
5	Check fast or fast.next null?	Node 3	null	fast.next is null	No cycle, exit loop

💡 fast pointer reached null, no cycle detected

Variable Tracker

Variable	Start	After Step 2	After Step 4	Final
slow	Node 1	Node 2	Node 3	Node 3
fast	Node 1	Node 3	null	null

Key Moments - 3 Insights

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

Moving fast pointer twice as fast ensures if a cycle exists, fast will eventually catch slow inside the loop (see execution_table steps 2 and 4).

What if fast or fast.next becomes null?

It means the list ends without cycle, so we stop checking and return false (see execution_table step 5).

Why do we check slow == fast after moving pointers?

Because meeting means cycle detected; checking after moves ensures we detect cycle as soon as pointers meet (see execution_table step 3).

Visual Quiz - 3 Questions

Look at the execution_table, what node is the slow pointer at after step 2?

A Node 1

B Node 2

C Node 3

D null

💡 Hint

Check the 'slow Pointer Node' column at step 2 in execution_table.

At which step does the fast pointer reach the end (null)?

A Step 4

B Step 3

C Step 5

D Step 2

💡 Hint

Look at the 'fast Pointer Node' column and pointer changes in execution_table.

If the linked list had a cycle, what would happen to the slow and fast pointers?

A They would never meet

B Fast pointer would become null

C They would meet at some node inside the cycle

D Slow pointer would become null

💡 Hint

Refer to concept_flow and key_moments about pointer meeting in cycle.

Concept Snapshot

Detect cycle by using two pointers: slow moves 1 step, fast moves 2 steps.
If slow == fast at any point, cycle exists.
If fast or fast.next is null, no cycle.
Efficient O(n) time, O(1) space.
Known as Floyd's Cycle Detection Algorithm.

Full Transcript

This concept uses two pointers starting at the head of the linked list. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If the linked list has a cycle, the fast pointer will eventually catch up to the slow pointer inside the cycle. If the fast pointer reaches the end of the list (null), it means there is no cycle. The execution table shows each step with pointer positions and the linked list state. Key moments clarify why pointers move at different speeds and when to stop. The visual quiz tests understanding of pointer positions and cycle detection logic.

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