Detect Cycle in Linked List Floyd's Algorithm in DSA Java

Mental Model

Use two pointers moving at different speeds to find if a loop exists by checking if they meet.

Analogy: Imagine two runners on a circular track: one runs fast and the other slow. If the track loops, the fast runner will eventually catch the slow runner.

head -> [1] -> [2] -> [3] -> [4] -> [5] -> null
                     ↑                   ↓
                     ←-------------------

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5 with a cycle from 5 back to 3

Goal: Detect if the linked list has a cycle using Floyd's algorithm

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

head -> [slow->1, fast->1] -> 2 -> 3 -> 4 -> 5 -> (cycle back to 3)

Why: Start both pointers at the beginning to begin traversal

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

head -> 1 -> [slow->2] -> [fast->3] -> 4 -> 5 -> (cycle back to 3)

Why: Slow moves one step, fast moves two steps to detect cycle faster

Step 3: Move slow to node 3, fast to node 5

head -> 1 -> 2 -> [slow->3] -> 4 -> [fast->5] -> (cycle back to 3)

Why: Pointers advance to check if they meet inside the cycle

Step 4: Move slow to node 4, fast moves two steps: from 5 -> 3 -> 4

head -> 1 -> 2 -> 3 -> [slow->4, fast->4] -> 5 -> (cycle back to 3)

Why: Fast pointer loops back due to cycle, slow pointer moves forward. They meet at node 4

Step 5: slow == fast at node 4, cycle detected and return true

head -> 1 -> 2 -> 3 -> [slow->4, fast->4] -> 5 -> (cycle back to 3)

Why: Both pointers meet at node 4, confirming a cycle

Result:

Cycle detected because slow and fast pointers meet at node 4

Annotated Code

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class DetectCycleFloyd {
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false; // empty or single node no cycle
        ListNode slow = head;
        ListNode 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 detected
        }
        return false; // fast reached end, no cycle
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        // create cycle: 5 -> 3
        head.next.next.next.next.next = head.next.next;

        System.out.println(hasCycle(head));
    }
}

if (head == null || head.next == null) return false; // empty or single node no cycle

handle edge cases where cycle is impossible

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 to detect cycle faster

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

check if pointers meet indicating a cycle

Output

true

Complexity Analysis

Time: O(n) because each pointer traverses nodes at most once until they meet or reach the end

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), Floyd's algorithm uses constant space making it more efficient

Edge Cases

empty list

returns false immediately as no nodes exist

DSA Java

if (head == null || head.next == null) return false; // empty or single node no cycle

single node without cycle

returns false because no cycle can form

DSA Java

if (head == null || head.next == null) return false; // empty or single node no cycle

list with cycle at head

detects cycle when slow and fast pointers meet at head or inside loop

DSA Java

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

When to Use This Pattern

When you need to detect a cycle in a linked list efficiently without extra space, Floyd's cycle detection is the go-to pattern because it uses two pointers moving at different speeds to find loops.

Common Mistakes

Mistake: Moving fast pointer by one step instead of two, causing failure to detect cycle correctly
Fix: Ensure fast pointer moves two steps each iteration to catch up with slow pointer inside the cycle

Mistake: Not checking if fast or fast.next is null before moving fast pointer, causing null pointer errors
Fix: Add condition in while loop to check fast != null && fast.next != null before advancing pointers

Summary

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

Use when you want to find cycles in linked lists efficiently without extra memory.

If a cycle exists, the fast pointer will eventually meet the slow pointer inside the loop.

Practice

1. What is the main idea behind Floyd's Cycle Detection Algorithm in a linked list?

easy

A. Use two pointers moving at different speeds to detect a cycle

B. Count the number of nodes and check if it exceeds a limit

C. Reverse the linked list and check if it matches the original

D. Use a hash set to store visited nodes

Solution

1. Step 1: Understand Floyd's Algorithm concept

   It uses two pointers: a slow pointer moving one step at a time and a fast pointer moving two steps at a time.

2. Step 2: Detect cycle by pointer meeting

   If there is a cycle, the fast pointer will eventually meet the slow pointer inside the loop.

3. Final Answer:

   Use two pointers moving at different speeds to detect a cycle -> Option A

4. Quick Check:

   Two pointers at different speeds detect cycle [OK]

Hint: Two pointers moving at different speeds detect cycle [OK]

Common Mistakes:

• Thinking counting nodes detects cycle
• Assuming reversing list helps detect cycle
• Using extra memory instead of pointers

2. Which of the following is the correct way to initialize the slow and fast pointers in Floyd's cycle detection in Java?

easy

A. ListNode slow = head; ListNode fast = head.next;

B. ListNode slow = head.next; ListNode fast = head.next.next;

C. ListNode slow = head; ListNode fast = head;

D. ListNode slow = null; ListNode fast = head;

Solution

1. Step 1: Initialize both pointers at head

   Both slow and fast pointers start at the head node to begin traversal.

2. Step 2: Move pointers at different speeds

   Slow moves one step, fast moves two steps from the same start point.

3. Final Answer:

   ListNode slow = head; ListNode fast = head; -> Option C

4. Quick Check:

   Both pointers start at head [OK]

Hint: Start both pointers at head for Floyd's algorithm [OK]

Common Mistakes:

• Starting fast pointer ahead causing null errors
• Initializing slow pointer as null
• Starting pointers at different nodes incorrectly

3. What will be the output of the following Java code snippet detecting cycle using Floyd's algorithm?

class ListNode {
  int val;
  ListNode next;
  ListNode(int val) { this.val = val; this.next = null; }
}

public class Test {
  public static boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) return true;
    }
    return false;
  }

  public static void main(String[] args) {
    ListNode a = new ListNode(1);
    ListNode b = new ListNode(2);
    ListNode c = new ListNode(3);
    a.next = b; b.next = c; c.next = b;
    System.out.println(hasCycle(a));
  }
}

medium

A. false

B. true

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze the linked list structure

   Node c points back to node b, creating a cycle in the list.

2. Step 2: Floyd's algorithm detects cycle

   Slow and fast pointers will meet inside the cycle, so method returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Cycle exists, so output is true [OK]

Hint: Cycle means slow and fast pointers meet [OK]

Common Mistakes:

• Assuming no cycle because list looks linear
• Confusing output with false
• Ignoring pointer movement conditions

4. Identify the bug in this Floyd's cycle detection code snippet:

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

medium

A. The return false statement is missing

B. slow pointer should move two steps instead of one

C. The while loop condition is incorrect

D. fast pointer should start at head, not head.next

Solution

1. Step 1: Check pointer initialization

   Fast pointer starts at head.next, which can cause missing cycle detection if list has only one node.

2. Step 2: Correct initialization for reliable detection

   Both slow and fast pointers should start at head to ensure proper cycle detection.

3. Final Answer:

   fast pointer should start at head, not head.next -> Option D

4. Quick Check:

   Start both pointers at head [OK]

Hint: Initialize both pointers at head to avoid missing cycles [OK]

Common Mistakes:

• Starting fast pointer ahead causing missed cycles
• Changing slow pointer speed incorrectly
• Incorrect loop condition usage

5. Given a linked list where a cycle exists, how can Floyd's algorithm be extended to find the exact node where the cycle begins? Choose the correct approach.

hard

A. After detecting cycle, reset slow to head and move both pointers one step until they meet

B. Count the number of nodes in the cycle and move slow pointer that many steps

C. Reverse the linked list and check for repeated nodes

D. Use a hash set to store nodes and find the first repeated node

Solution

1. Step 1: Detect cycle using Floyd's algorithm

   When slow and fast pointers meet, a cycle is confirmed.

2. Step 2: Reset slow pointer to head and move both pointers one step

   Move slow and fast pointers one step at a time; the node where they meet is the cycle start.

3. Final Answer:

   After detecting cycle, reset slow to head and move both pointers one step until they meet -> Option A

4. Quick Check:

   Reset slow and move both pointers to find cycle start [OK]

Hint: Reset slow to head, move both pointers one step to find cycle start [OK]

Common Mistakes:

• Trying to find cycle start without resetting slow pointer
• Counting nodes instead of pointer movement
• Using extra memory unnecessarily