Detect if a Linked List is Circular in DSA C# - Execution Trace

Concept Flow - Detect if a Linked List is Circular

Start at head node

↓

Initialize slow and fast pointers

↓

Move slow by 1 step

↓

Move fast by 2 steps

↓

Check if slow == fast?

Yes→List is Circular

No↓

Check if fast or fast.next is null?

Yes→List is NOT Circular

↩Back to Move slow by 1 step

Use two pointers moving at different speeds to detect if they meet, indicating a circular linked list.

Execution Sample

DSA C#

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;

This code uses two pointers moving through the list at different speeds to detect a cycle.

Execution Table

Step	Operation	Slow Pointer Node	Fast Pointer Node	Pointer Changes	Visual State
1	Initialize pointers	Node1	Node1	slow = head, fast = head	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
2	Move slow by 1, fast by 2	Node2	Node3	slow = Node2, fast = Node3	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
3	Move slow by 1, fast by 2	Node3	Node2	slow = Node3, fast = Node2	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
4	Check slow == fast?	Node3	Node2	No match	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
5	Move slow by 1, fast by 2	Node4	Node4	slow = Node4, fast = Node4	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
6	Check slow == fast?	Node4	Node4	Match found	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
7	Return true	-	-	-	Cycle detected

💡 Pointers met at Node4, confirming the list is circular.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	Final
slow	Node1	Node2	Node3	Node4	Node4	Node4
fast	Node1	Node3	Node2	Node4	Node4	Node4

Key Moments - 3 Insights

Why do we move 'fast' pointer by two steps and 'slow' pointer by one step?

Moving 'fast' twice as fast as 'slow' ensures that if a cycle exists, they will eventually meet inside the loop, as shown in steps 2, 3, and 5 of the execution_table.

What happens if the list is not circular?

If the list is not circular, 'fast' or 'fast.next' will become null, causing the loop to exit and return false. This is not shown here but is the exit condition in the code.

Why do we check 'slow == fast' after moving the pointers?

Checking 'slow == fast' after moving pointers detects if both pointers point to the same node, indicating a cycle, as seen in steps 6 and 7.

Visual Quiz - 3 Questions

Look at the execution_table, at which step do slow and fast pointers first point to the same node?

A Step 4

B Step 6

C Step 5

D Step 3

💡 Hint

Check the 'Check slow == fast?' operation and the 'Pointer Changes' column in execution_table rows.

According to variable_tracker, what node is 'fast' pointing to after Step 3?

A Node3

B Node2

C Node4

D Node1

💡 Hint

Look at the 'fast' row and 'After Step 3' column in variable_tracker.

If the linked list had no cycle, what would happen to the 'fast' pointer?

A It would eventually become null or its next would be null

B It would meet slow pointer at some node

C It would keep moving forever

D It would move only one step at a time

💡 Hint

Refer to the exit condition in the code and explanation in key_moments about non-circular lists.

Concept Snapshot

Detect Circular Linked List using two pointers:
- Initialize slow and fast at head
- Move slow by 1 step, fast by 2 steps
- If slow == fast, list is circular
- If fast or fast.next is null, list is not circular
- Time: O(n), Space: O(1)

Full Transcript

To detect if a linked list is circular, we use two pointers starting at the head node. The slow pointer moves one step at a time, while the fast pointer moves two steps. If the list has a cycle, these pointers will eventually meet at the same node. If the fast pointer reaches the end (null), the list is not circular. This method efficiently detects cycles without extra memory.

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