Detect Cycle in Linked List Floyd's Algorithm in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Floyd's Cycle Detection Algorithm in a linked list?

It uses two pointers moving at different speeds (slow and fast). If there is a cycle, the fast pointer will eventually meet the slow pointer inside the cycle.

beginner

In Floyd's Algorithm, what speeds do the two pointers move at?

The slow pointer moves one step at a time, and the fast pointer moves two steps at a time.

intermediate

Why does the fast pointer eventually meet the slow pointer if a cycle exists?

Because the fast pointer moves faster, it will catch up to the slow pointer inside the loop, similar to two runners on a circular track where the faster runner laps the slower one.

beginner

What does it mean if the fast pointer reaches the end (null) in Floyd's Algorithm?

It means there is no cycle in the linked list because the fast pointer reached the end without meeting the slow pointer.

intermediate

How can you find the starting node of the cycle after detecting a cycle using Floyd's Algorithm?

After the slow and fast pointers meet, reset one pointer to the head. Then move both pointers one step at a time. The node where they meet again is the start of the cycle.

In Floyd's Cycle Detection Algorithm, what happens if the linked list has no cycle?

A Fast pointer reaches null without meeting slow pointer

B Slow pointer moves faster than fast pointer

C Fast pointer meets slow pointer immediately

D Both pointers move at the same speed

If there is no cycle, the fast pointer will reach the end (null) without ever meeting the slow pointer.

What is the speed of the fast pointer in Floyd's Algorithm?

A One step at a time

B Two steps at a time

C Three steps at a time

D Variable speed

The fast pointer moves two steps at a time to catch the slow pointer if a cycle exists.

After detecting a cycle, how do you find the cycle's starting node?

A Move both pointers at different speeds from the meeting point

B Move fast pointer to null

C Reset one pointer to head and move both one step at a time until they meet

D Move slow pointer two steps at a time

Resetting one pointer to head and moving both one step at a time leads them to meet at the cycle's start.

Why does Floyd's Algorithm use two pointers instead of one?

A To reduce memory usage

B To sort the linked list

C To reverse the linked list

D To detect cycles efficiently by comparing positions

Two pointers moving at different speeds help detect cycles efficiently by checking if they meet.

What is the time complexity of Floyd's Cycle Detection Algorithm?

A O(n)

B O(n log n)

C O(n^2)

D O(1)

The algorithm runs in linear time O(n) because each pointer moves through the list at most a few times.

Explain how Floyd's Cycle Detection Algorithm works to find if a linked list has a cycle.

Think of two runners on a track running at different speeds.

Describe the steps to find the starting node of a cycle after detecting a cycle using Floyd's Algorithm.

Reset and move pointers slowly to find cycle start.

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