Detect Cycle in Linked List Floyd's Algorithm in DSA C# - Time & Space Complexity

Time Complexity: Detect Cycle in Linked List Floyd's Algorithm

O(n)

Understanding Time Complexity

We want to understand how long it takes to check if a linked list has a cycle using Floyd's Algorithm.

How does the time needed grow as the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code checks if a linked list has a cycle by moving two pointers at different speeds.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves slow and fast pointers through the list.
• How many times: At most, the fast pointer moves through all nodes, so up to n times where n is the list length.

How Execution Grows With Input

As the list gets longer, the number of steps grows roughly in a straight line with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The time grows linearly as the list size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to detect a cycle grows directly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Because there are two pointers, the time is doubled or squared."

[OK] Correct: The fast pointer moves twice as fast, but both pointers together still only pass through the list a limited number of times, so time grows linearly, not squared.

Interview Connect

Understanding this time complexity helps you explain why Floyd's Algorithm is efficient and preferred for cycle detection in linked lists.

Self-Check

"What if we used only one pointer and checked each node against all others? How would the time complexity change?"

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