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

Concept Flow - Detect if a Linked List is Circular

Start at head node

↓

Initialize two pointers: slow and fast

↓

Move slow by 1 step, fast by 2 steps

↓

Check if fast or fast.next is null?

Yes→No cycle, return false

No↓

Check if slow == fast?

Yes→Cycle detected, return true

↩Back to move pointers step

Start with two pointers moving at different speeds; if they meet, the list is circular; if fast pointer reaches null, it's not.

Execution Sample

DSA Java

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 at different speeds to detect a cycle in the linked list.

Execution Table

Step	Operation	slow Pointer	fast Pointer	Check Condition	Cycle Detected?	Visual State
1	Initialize pointers	Node1	Node1	fast != null && fast.next != null = true	No	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
2	Move pointers	Node2	Node3	fast != null && fast.next != null = true	No	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
3	Move pointers	Node3	Node4	fast != null && fast.next != null = true	No	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
4	Move pointers	Node4	Node2	fast != null && fast.next != null = true	No	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
5	Move pointers	Node2	Node4	fast != null && fast.next != null = true	No	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
6	Move pointers	Node3	Node2	fast != null && fast.next != null = true	No	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
7	Move pointers	Node4	Node4	fast != null && fast.next != null = true	Yes	Node1 -> Node2 -> Node3 -> Node4 -> Node2 (cycle)
8	Return true	-	-	-	Yes	Cycle detected, stop

💡 Pointers slow and fast met at Node4, confirming a cycle in the list.

Variable Tracker

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

Key Moments - 3 Insights

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

Moving 'fast' two steps and 'slow' one step ensures that if a cycle exists, they will eventually meet inside the cycle, as shown in execution_table rows 2-7.

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, as checked in the condition in execution_table row 1.

Why do we check 'fast != null && fast.next != null' before moving pointers?

This check prevents null pointer errors and ensures we don't move beyond the list end, which would mean no cycle, as seen in the condition column of execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, at which step do slow and fast pointers first meet?

A Step 2

B Step 7

C Step 3

D Step 8

💡 Hint

Check the 'Cycle Detected?' column where slow == fast is true.

According to variable_tracker, what is the position of 'fast' pointer after Step 3?

A Node3

B Node2

C Node4

D Node1

💡 Hint

Look at the 'fast' row under 'After Step 3' column.

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

A It would eventually become null or fast.next would be null

B It would meet slow pointer at some node

C It would move only one step at a time

D It would cause an infinite loop

💡 Hint

Refer to the condition check in concept_flow and execution_table row 1.

Concept Snapshot

Detect cycle in linked list using two pointers:
- Initialize slow and fast at head
- Move slow by 1 step, fast by 2 steps
- If fast or fast.next is null, no cycle
- If slow meets fast, cycle detected
- Return true if cycle, else false

Full Transcript

To detect if a linked list is circular, we use two pointers starting at the head. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If the list has a cycle, these pointers will eventually meet inside the cycle. If the fast pointer reaches the end of the list (null), then 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 last node points back to one of the previous nodes, forming a loop

C. The linked list has no nodes

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 B

4. Quick Check:

   Circular linked list = last node points back [OK]

Hint: Circular means last node links back to earlier node [OK]

Common Mistakes:

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

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

easy

A. while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; }

B. while (slow != null) { slow = slow.next; if (slow == fast) return true; }

C. for (int i = 0; i < size; i++) { if (node == null) return false; node = node.next; }

D. if (head == null) return true; else 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 meeting point

   If slow and fast pointers meet, the list is circular; otherwise, if fast reaches null, it's not circular.

3. Final Answer:

   while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } -> Option A

4. Quick Check:

   Two pointers meet = circular [OK]

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

Common Mistakes:

• Not checking fast.next for null
• Using only one pointer to detect loop
• Returning true when list is empty

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

class Node { int data; Node next; Node(int d) { data = d; next = null; } }
public class Test {
  public static boolean isCircular(Node head) {
    if (head == null) return false;
    Node slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
      if (slow == fast) return true;
      slow = slow.next;
      fast = fast.next.next;
    }
    return false;
  }
  public static void main(String[] args) {
    Node head = new Node(1);
    head.next = new Node(2);
    head.next.next = new Node(3);
    head.next.next.next = head; // circular link
    System.out.println(isCircular(head));
  }
}

medium

A. Runtime exception

B. false

C. Compilation error

D. true

Solution

1. Step 1: Understand the linked list structure

   The list has nodes 1 -> 2 -> 3, and then 3 points back to 1, making it circular.

2. Step 2: Trace the isCircular method

   Slow starts at 1, fast at 2. They move until they meet because of the loop, so method returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Loop present = true [OK]

Hint: If fast and slow meet, list is circular [OK]

Common Mistakes:

• Starting fast pointer incorrectly
• Not creating circular link properly
• Confusing output with false

4. Identify the bug in this code snippet that tries to detect if a linked list is circular:

public boolean isCircular(Node head) {
  Node slow = head, fast = head;
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow.next == fast.next) return true;
  }
  return false;
}

medium

A. slow pointer should start at head.next

B. fast pointer should move only one step at a time

C. The condition should compare slow and fast, not slow.next and fast.next

D. The loop condition should be while (slow != null)

Solution

1. Step 1: Analyze pointer comparison

   The code compares slow.next and fast.next, but to detect loop, slow and fast themselves must be compared.

2. Step 2: Correct the comparison

   Change if condition to if (slow == fast) to detect when pointers meet inside the loop.

3. Final Answer:

   The condition should compare slow and fast, not slow.next and fast.next -> Option C

4. Quick Check:

   Compare slow and fast pointers directly [OK]

Hint: Compare slow and fast nodes directly to detect loop [OK]

Common Mistakes:

• Comparing next nodes instead of current nodes
• Moving fast pointer incorrectly
• Wrong loop condition

5. Given a linked list where the last node points to the head node, how can you modify the detection method to also return the length of the loop?

hard

A. After detecting the loop with slow == fast, keep slow fixed and move fast until it meets slow again, counting steps

B. Count nodes from head to tail without checking for loop

C. Return the total number of nodes visited before fast reaches null

D. Use a hash set to store nodes and count unique nodes only

Solution

1. Step 1: Detect loop using two pointers

   Use Floyd's cycle detection to find when slow equals fast inside the loop.

2. Step 2: Count loop length

   Keep slow pointer fixed, move fast pointer one step at a time, incrementing count until fast meets slow again.

3. Final Answer:

   After detecting the loop with slow == fast, keep slow fixed and move fast until it meets slow again, counting steps -> Option A

4. Quick Check:

   Count steps in loop after detection [OK]

Hint: Count nodes in loop by moving one pointer until it meets again [OK]

Common Mistakes:

• Counting nodes before loop detection
• Using total nodes instead of loop length
• Not moving pointer correctly to count loop