Detect if a Linked List is Circular in DSA Java

Mental Model

A linked list is circular if you can keep following next pointers and eventually come back to the start.

Analogy: Imagine walking on a path that loops back to where you started instead of ending; you know it's circular because you return to the start point.

head -> 1 -> 2 -> 3 -> null  (non-circular)
head -> 1 -> 2 -> 3 -> ↑ (points back to 1, circular)

Dry Run Walkthrough

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

Goal: Detect if the linked list loops back to an earlier node, making it circular

Step 1: start slow and fast pointers at head (node 1)

head -> [slow->1, fast->1] -> 2 -> 3 -> 4 -> 2 (loop)

Why: We use two pointers to detect a cycle by moving at different speeds

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

head -> 1 -> [slow->2] -> [fast->3] -> 4 -> 2 (loop)

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

Step 3: move slow to node 3, fast moves two steps: 4 then back to 2 (loop)

head -> 1 -> 2 -> [slow->3] -> [fast->2] -> 3 -> 4 (loop)

Why: Fast pointer loops back due to cycle, slow moves forward

Step 4: move slow to node 4, fast moves two steps: 3 then 4

head -> 1 -> 2 -> 3 -> [slow->4] -> [fast->4] -> 2 (loop)

Why: Slow and fast pointers meet at node 4, confirming cycle

Result:

head -> 1 -> 2 -> 3 -> 4 -> (loops back to 2)
Cycle detected: true

Annotated Code

DSA Java

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

    public static boolean isCircular(Node head) {
        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; // pointers meet, cycle found
        }
        return false; // fast reached end, no cycle
    }

    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 = new Node(4);
        // create cycle: node 4 points back to node 2
        head.next.next.next.next = head.next;

        boolean result = isCircular(head);
        System.out.println("Cycle detected: " + result);
    }
}

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

handle empty list edge case

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

loop while fast pointer can move ahead

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; // pointers meet, cycle found

detect cycle when pointers meet

return false; // fast reached end, no cycle

no cycle if fast pointer reaches list end

Output

Cycle detected: true

Complexity Analysis

Time: O(n) because slow and fast pointers traverse nodes at most once until they meet or reach end

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

vs Alternative: Compared to using a hash set to store 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 Java

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 Java

if (slow == fast) return true; // pointers meet, cycle found

list with no cycle

returns false after fast pointer reaches null

DSA Java

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

When to Use This Pattern

When you see a problem asking if a linked list loops back to an earlier node, use the slow and fast pointer technique to detect cycles efficiently.

Common Mistakes

Mistake: Checking only if fast pointer is null without checking fast.next causes null pointer errors.
Fix: Always check both fast != null and fast.next != null before moving fast pointer two steps.

Mistake: Moving slow and fast pointers incorrectly (e.g., both by one step) misses cycle detection.
Fix: Move slow by one step and fast by two steps to ensure they meet if cycle exists.

Summary

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

Use when you need to know if following next pointers 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 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