Detect Cycle in Linked List Floyd's Algorithm in DSA C#

Mental Model

Use two pointers moving at different speeds to find if a loop exists in a linked list.

Analogy: Imagine two runners on a circular track: one runs fast and the other slow. If the track is a loop, the fast runner will eventually catch the slow runner.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑
fast ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5 with a cycle from 5 back to 3

Goal: Detect if the linked list has a cycle using Floyd's algorithm

Step 1: Initialize slow and fast pointers at head (node 1)

1 -> 2 -> 3 -> 4 -> 5 ->
          ↑     ↑
        slow  fast

Why: Both pointers start at the beginning to begin traversal

Step 2: Move slow by 1 step to node 2, fast by 2 steps to node 3

1 -> 2 -> 3 -> 4 -> 5 ->
               ↑     ↑
             slow  fast

Why: Slow moves one step, fast moves two steps to detect cycle faster

Step 3: Move slow by 1 step to node 3, fast by 2 steps to node 5

1 -> 2 -> 3 -> 4 -> 5 ->
                    ↑     ↑
                  slow  fast

Why: Pointers continue moving; fast pointer jumps ahead

Step 4: Move slow by 1 step to node 4, fast moves 2 steps but cycles back to node 4

1 -> 2 -> 3 -> 4 -> 5 ->
                    ↑     ↑
                  slow  fast

Why: Fast pointer loops back due to cycle, slow pointer moves forward

Step 5: Slow and fast pointers meet at node 4, cycle detected

1 -> 2 -> 3 -> 4 -> 5 ->
                    ↑
                 slow=fast

Why: Meeting point confirms presence of a cycle

Result:

1 -> 2 -> 3 -> 4 -> 5 -> (cycle back to 3)
Cycle detected: true

Annotated Code

DSA C#

using System;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public bool HasCycle(ListNode head) {
        if (head == null) return false;
        ListNode slow = head;
        ListNode 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
    }
}

public class Program {
    public static void Main() {
        // Create nodes
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        // Link nodes
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node3; // cycle here

        Solution sol = new Solution();
        bool result = sol.HasCycle(node1);
        Console.WriteLine("Cycle detected: " + result);
    }
}

if (head == null) return false;

handle empty list edge case

while (fast != null && fast.next != null) {

loop while fast pointer and next exist to avoid null errors

slow = slow.next; // move slow by 1

advance slow pointer by one node

fast = fast.next.next; // move fast by 2

advance fast pointer by two nodes

if (slow == fast) { return true; }

if pointers meet, cycle exists

Output

Cycle detected: True

Complexity Analysis

Time: O(n) because both pointers traverse the list at most once until they meet or reach the end

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Compared to using a hash set to store visited nodes (O(n) space), Floyd's algorithm uses constant space making it more efficient

Edge Cases

empty list (head is null)

returns false immediately, no cycle

DSA C#

if (head == null) return false;

single node without cycle

fast or fast.next becomes null, returns false

DSA C#

while (fast != null && fast.next != null)

single node with cycle (node points to itself)

slow and fast meet at the node, returns true

DSA C#

if (slow == fast) { return true; }

When to Use This Pattern

When you need to detect a cycle in a linked list efficiently, Floyd's algorithm is the go-to because it uses two pointers moving at different speeds to find loops without extra memory.

Common Mistakes

Mistake: Moving the fast pointer by only one step instead of two
Fix: Advance fast pointer by two steps to ensure it moves faster than slow

Mistake: Not checking if fast or fast.next is null before moving fast pointer
Fix: Add condition to check fast != null && fast.next != null before advancing fast

Mistake: Returning false too early without completing the loop
Fix: Only return false after the loop ends without pointers meeting

Summary

Detects if a linked list has a cycle by using two pointers moving at different speeds.

Use when you want to find cycles in linked lists efficiently without extra memory.

If a cycle exists, the fast pointer will eventually catch the slow pointer inside the loop.

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