Detect Cycle in Linked List Floyd's Algorithm in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this code detecting a cycle in a linked list?

Consider a linked list where a cycle is created by connecting the last node back to the second node. What will the following C# code print?

DSA C#

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

public class LinkedListCycle {
    public static bool HasCycle(Node head) {
        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;
    }

    public static void Main() {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = head.next; // cycle here
        bool result = HasCycle(head);
        System.Console.WriteLine(result);
    }
}

A Compilation error

B True

C False

D Runtime exception

💡 Hint

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

The fast pointer moves two steps and the slow pointer moves one step. If there is a cycle, they will eventually meet, so the function returns true.

❓ Predict Output

intermediate

What is the output when no cycle exists in the linked list?

Given a linked list with nodes 1 -> 2 -> 3 -> 4 -> null (no cycle), what will the following code print?

DSA C#

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

public class LinkedListCycle {
    public static bool HasCycle(Node head) {
        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;
    }

    public static void Main() {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        bool result = HasCycle(head);
        System.Console.WriteLine(result);
    }
}

A False

B Compilation error

C NullReferenceException

D True

💡 Hint

If the fast pointer reaches the end, no cycle exists.

Since the list ends with null and no cycle is formed, the fast pointer reaches null and the function returns false.

🔧 Debug

advanced

What error does this code raise when detecting a cycle?

Analyze the following code snippet. What error will it raise when run?

DSA C#

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

public class LinkedListCycle {
    public static bool HasCycle(Node head) {
        Node slow = head;
        Node fast = head.next.next; // potential problem here
        while (fast != null && fast.next != null) {
            if (slow == fast) return true;
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

    public static void Main() {
        Node head = new Node(1);
        bool result = HasCycle(head);
        System.Console.WriteLine(result);
    }
}

A IndexOutOfRangeException

B Compilation error

C NullReferenceException

D No error, prints False

💡 Hint

Check how fast pointer is initialized and if it can be null.

The fast pointer is initialized as head.next.next without checking if head.next or head.next.next is null, causing NullReferenceException if the list is too short.

🧠 Conceptual

advanced

Why does Floyd's algorithm use two pointers moving at different speeds?

What is the main reason Floyd's cycle detection algorithm uses a slow pointer moving one step and a fast pointer moving two steps?

A To ensure the fast pointer will eventually catch the slow pointer if a cycle exists

B To reduce memory usage by avoiding extra data structures

C To sort the linked list while detecting cycles

D To reverse the linked list during traversal

💡 Hint

Think about how two pointers moving at different speeds behave in a cycle.

If a cycle exists, the fast pointer moves faster and will eventually meet the slow pointer inside the cycle, confirming the cycle's presence.

🚀 Application

expert

What is the output after removing the cycle from a linked list?

Given a linked list with a cycle created by connecting the last node back to the third node, the following code detects and removes the cycle. What will be the printed linked list after removal?

DSA C#

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

public class LinkedListCycle {
    public static bool DetectAndRemoveCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                RemoveCycle(head, slow);
                return true;
            }
        }
        return false;
    }

    private static void RemoveCycle(Node head, Node meetingPoint) {
        Node ptr1 = head;
        Node ptr2 = meetingPoint;
        while (ptr1.next != ptr2.next) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        ptr2.next = null;
    }

    public static void PrintList(Node head) {
        Node current = head;
        while (current != null) {
            System.Console.Write(current.val + " -> ");
            current = current.next;
        }
        System.Console.WriteLine("null");
    }

    public static void Main() {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = head.next.next; // cycle to node 3

        bool hasCycle = DetectAndRemoveCycle(head);
        PrintList(head);
    }
}

A Runtime exception due to infinite loop

B 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 4 -> 5 -> ... (infinite loop)

C 1 -> 2 -> 3 -> null

D 1 -> 2 -> 3 -> 4 -> 5 -> null

💡 Hint

After removal, the list should end with null and no cycles.

The code detects the cycle and removes it by setting the last node's next to null. The printed list ends at 5 with null.

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