Detect if a Linked List is Circular in DSA C#

Mental Model

A circular linked list loops back to an earlier node instead of ending with null. We want to find if such a loop exists.

Analogy: Imagine a race track where runners keep running in circles. If the track loops back to the start, it's circular; if it ends, it's not.

1 -> 2 -> 3 -> 4 -> null

Circular:
1 -> 2 -> 3 -> 4 ->
          ↑       ↓
          ← ← ← ← ←

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4, with node 4 pointing back to node 2 (circular)

Goal: Detect if the linked list has a cycle (circular reference)

Step 1: Initialize two pointers: slow at node 1, fast at node 1

[slow->1] -> 2 -> 3 -> 4 ->
[fast->1] -> 2 -> 3 -> 4 ->

Why: Start both pointers at head to begin cycle detection

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

1 -> [slow->2] -> 3 -> 4 ->
1 -> 2 -> [fast->3] -> 4 ->

Why: Fast pointer moves twice as fast to catch slow if cycle exists

Step 3: Move slow by 1 step to node 3, fast by 2 steps to node 2 (due to cycle)

1 -> 2 -> [slow->3] -> 4 ->
1 -> 2 -> 3 -> 4 -> [fast->2] ->

Why: Fast pointer loops back because of cycle, slow moves forward

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

1 -> 2 -> 3 -> [slow->4] ->
1 -> 2 -> [fast->4] ->

Why: Both pointers meet at node 4, confirming cycle

Result:

Cycle detected because slow and fast pointers met at node 4

Annotated Code

DSA C#

using System;

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

public class LinkedList
{
    public Node head;

    public bool IsCircular()
    {
        if (head == null) return false; // empty list can't be circular

        Node slow = head;
        Node 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; // reached end, no cycle
    }
}

public class Program
{
    public static void Main()
    {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(4);

        // Creating a cycle: node 4 points back to node 2
        list.head.next.next.next.next = list.head.next;

        Console.WriteLine(list.IsCircular() ? "Cycle detected" : "No cycle");
    }
}

if (head == null) return false; // empty list can't be circular

handle empty list edge case

Node slow = head; Node fast = head;

initialize two pointers at head

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

loop while fast pointer can move ahead safely

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; // cycle detected }

if pointers meet, cycle exists

return false; // reached end, no cycle

no cycle found if fast pointer reaches null

Output

Cycle detected

Complexity Analysis

Time: O(n) because in worst case we traverse all nodes once with two pointers

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

vs Alternative: Compared to using a hash set to track visited nodes (O(n) space), this uses constant space and is more efficient

Edge Cases

empty list

returns false immediately because no nodes exist

DSA C#

if (head == null) return false; // empty list can't be circular

single node pointing to itself

detects cycle because slow and fast meet at the single node

DSA C#

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

list with no cycle

returns false after fast pointer reaches null

DSA C#

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

When to Use This Pattern

When you see a problem asking if a linked list loops back on itself, use the two-pointer (slow and fast) technique to detect cycles efficiently.

Common Mistakes

Mistake: Checking only if slow == fast without ensuring fast and fast.next are not null
Fix: Add condition in while loop to check fast != null && fast.next != null before moving pointers

Mistake: Moving slow and fast pointers incorrectly (e.g., both by one step)
Fix: Move slow by one step and fast by two steps to detect cycle properly

Summary

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

Use when you need to know if a linked list loops back to an earlier node.

If two pointers moving at different speeds meet, the list is circular.

Practice

1. What does it mean if a linked list is circular?

easy

A. The linked list nodes are sorted in ascending order

B. The linked list has no nodes

C. The last node points back to one of the previous nodes, forming a loop

D. The linked list contains only one node

Solution

1. Step 1: Understand linked list structure

   A linked list is a chain of nodes where each node points to the next node.

2. Step 2: Define circular linked list

   If the last node points back to any previous node, it creates a loop, making the list circular.

3. Final Answer:

   The last node points back to one of the previous nodes, forming a loop -> Option C

4. Quick Check:

   Circular linked list = loop in nodes [OK]

Hint: Circular means last node links back inside list [OK]

Common Mistakes:

• Thinking circular means sorted list
• Confusing empty list with circular
• Assuming single node list is always circular

2. Which of the following C# code snippets correctly checks if a linked list is circular using two pointers?

easy

A. if (head == null) return true; else return false;

B. while (slow != null) { slow = slow.Next; if (slow == null) return true; } return false;

C. for (int i = 0; i < length; i++) { if (list[i] == list[length - 1]) return true; } return false;

D. while (fast != null && fast.Next != null) { slow = slow.Next; fast = fast.Next.Next; if (slow == fast) return true; } return false;

Solution

1. Step 1: Identify Floyd's cycle detection logic

   Two pointers move at different speeds: slow moves one step, fast moves two steps.

2. Step 2: Check for pointer meeting

   If slow and fast meet, a cycle exists; otherwise, if fast reaches null, no cycle.

3. Final Answer:

   while (fast != null && fast.Next != null) { slow = slow.Next; fast = fast.Next.Next; if (slow == fast) return true; } return false; -> Option D

4. Quick Check:

   Two-pointer cycle detection = while (fast != null && fast.Next != null) { slow = slow.Next; fast = fast.Next.Next; if (slow == fast) return true; } return false; [OK]

Hint: Use two pointers moving at different speeds [OK]

Common Mistakes:

• Checking only one pointer for null
• Using for loop on linked list nodes
• Returning true when list is empty

3. What will be the output of the following C# code snippet?

class Node { public int Data; public Node Next; public Node(int d) { Data = d; Next = null; } }
Node head = new Node(1);
head.Next = new Node(2);
head.Next.Next = new Node(3);
head.Next.Next.Next = head.Next;
bool IsCircular(Node node) {
  Node slow = node, fast = node;
  while (fast != null && fast.Next != null) {
    slow = slow.Next;
    fast = fast.Next.Next;
    if (slow == fast) return true;
  }
  return false;
}
Console.WriteLine(IsCircular(head));

medium

A. true

B. false

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze linked list structure

   Nodes 1 -> 2 -> 3, then 3 points back to node 2, creating a loop.

2. Step 2: Trace Floyd's cycle detection

   Slow and fast pointers will meet inside the loop, returning true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Loop detected = true [OK]

Hint: Loop means pointers meet inside list [OK]

Common Mistakes:

• Assuming no loop because list looks linear
• Confusing pointer equality with data equality
• Expecting false because of missing null check

4. Identify the bug in this C# method that tries to detect if a linked list is circular:

bool IsCircular(Node head) {
  Node slow = head, fast = head;
  while (fast != null) {
    slow = slow.Next;
    fast = fast.Next.Next;
    if (slow == fast) return true;
  }
  return false;
}

medium

A. Missing check for fast.Next being null before accessing fast.Next.Next

B. Slow pointer should move two steps instead of one

C. Should return false inside the loop instead of after

D. Head node should be initialized to null

Solution

1. Step 1: Review pointer movement and null checks

   fast moves two steps: fast = fast.Next.Next; must check fast.Next != null to avoid null reference.

2. Step 2: Identify missing null check

   Loop condition only checks fast != null, but fast.Next could be null causing runtime error.

3. Final Answer:

   Missing check for fast.Next being null before accessing fast.Next.Next -> Option A

4. Quick Check:

   Check fast.Next != null before fast.Next.Next [OK]

Hint: Always check fast and fast.Next for null before moving fast [OK]

Common Mistakes:

• Ignoring fast.Next null check
• Moving slow pointer two steps incorrectly
• Returning false too early inside loop

5. Given a linked list where some nodes may form multiple loops, which approach correctly detects if the list is circular and why?

public bool IsCircular(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;
}

hard

A. It fails because it only detects the first loop and misses others

B. Floyd's cycle detection works because fast pointer will eventually meet slow pointer in any loop

C. It requires extra memory to store visited nodes to detect multiple loops

D. It only works if the list has exactly one loop

Solution

1. Step 1: Understand Floyd's cycle detection behavior

   Fast and slow pointers move at different speeds; if any loop exists, they will meet inside it.

2. Step 2: Consider multiple loops scenario

   In a singly linked list, multiple loops cannot exist independently; any loop causes pointers to meet.

3. Final Answer:

   Floyd's cycle detection works because fast pointer will eventually meet slow pointer in any loop -> Option B

4. Quick Check:

   Any loop causes pointer meeting = true [OK]

Hint: One loop detection suffices; multiple loops can't exist singly [OK]

Common Mistakes:

• Thinking multiple loops can exist in singly linked list
• Believing extra memory is needed for loop detection
• Assuming method detects all loops separately