Detect Cycle in Linked List Floyd's Algorithm in DSA Java - Execution Trace

Concept Flow - Detect Cycle in Linked List Floyd's Algorithm

Start: head

↓

Initialize slow = head, fast = head

↓

Loop: fast != null and fast.next != null?

No→No cycle found, return false

Yes↓

Move slow by 1 step

↓

Move fast by 2 steps

↓

Check if slow == fast?

Yes→Cycle detected, return true

↩Back to Loop

The algorithm uses two pointers moving at different speeds to detect if a cycle exists by checking if they meet.

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 moves two pointers through the list at different speeds to find if they meet, indicating a cycle.

Execution Table

Step	Operation	slow Pointer	fast Pointer	Visual State	Pointer Changes
1	Initialize slow and fast to head	Node 1	Node 1	┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │──→ │ data:2 │──→ │ data:3 │ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ ... └────────┘ └────────┘ └────────┘	slow = head, fast = head
2	Check loop condition (fast != null && fast.next != null)	Node 1	Node 1	Same as step 1	No change
3	Move slow by 1 step	Node 2	Node 1	┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │──→ │ data:2 │──→ │ data:3 │ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ ... └────────┘ └────────┘ └────────┘	slow moves to Node 2
4	Move fast by 2 steps	Node 2	Node 3	┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │──→ │ data:2 │──→ │ data:3 │──→ ... └────────┘ └────────┘ └────────┘	fast moves to Node 3
5	Check if slow == fast	Node 2	Node 3	No cycle yet	No
6	Loop condition check	Node 2	Node 3	Same as step 4	No change
7	Move slow by 1 step	Node 3	Node 3	┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │──→ │ data:2 │──→ │ data:3 │ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ ... └────────┘ └────────┘ └────────┘	slow moves to Node 3
8	Move fast by 2 steps	Node 3	Node 3	Cycle formed: Node 3 points back to Node 2 ┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │──→ │ data:2 │──→ │ data:3 │ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ └────────┘ ↑ | +-----------+	fast moves to Node 3 (two steps: 3 → 2 → 3 due to cycle)
9	Check if slow == fast	Node 3	Node 3	Cycle detected	Yes - return true
10	Loop condition check	Node 3	Node 3	Same as step 8	No change
11	Move slow by 1 step	Node 2	Node 3	Cycle continues ┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │──→ │ data:2 │──→ │ data:3 │ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ └────────┘ ↑ | +-----------+	slow moves to Node 2
12	Move fast by 2 steps	Node 2	Node 2	slow and fast meet at Node 2	fast moves to Node 2
13	Check if slow == fast	Node 2	Node 2	Cycle detected	Yes - return true

💡 slow and fast pointers meet at Node 3, cycle detected

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 7	After Step 8	After Step 11	After Step 12	Final
slow	Node 1	Node 2	Node 2	Node 3	Node 3	Node 2	Node 2	Node 2
fast	Node 1	Node 1	Node 3	Node 3	Node 3	Node 3	Node 2	Node 2

Key Moments - 3 Insights

Why do we check both fast != null and fast.next != null in the loop condition?

Because fast moves two steps at a time, we must ensure fast and fast.next exist to avoid null pointer errors. See execution_table rows 2 and 6 where this condition is checked before moving pointers.

Why do slow and fast pointers meet if there is a cycle?

Because fast moves faster and will eventually catch up to slow inside the cycle. Execution_table rows 7-9 show slow and fast meeting at Node 3, confirming the cycle.

What happens if the list has no cycle?

Fast pointer will reach null or fast.next will be null, causing the loop to exit and return false. This is shown in the exit_note and loop condition checks in rows 2 and 6.

Visual Quiz - 3 Questions

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

A Step 1

B Step 3

C Step 7

D Step 11

💡 Hint

Check the 'slow Pointer' and 'fast Pointer' columns in execution_table rows 1 and 3.

At which step do slow and fast pointers meet indicating a cycle?

A Step 12

B Step 13

C Step 9

D Step 10

💡 Hint

Look at execution_table rows 8 and 9 where slow and fast pointers are equal.

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

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 loop infinitely

💡 Hint

Refer to the loop condition checks in execution_table rows 2 and 6.

Concept Snapshot

Detect Cycle in Linked List using Floyd's Algorithm:
- Use two pointers: slow (1 step), fast (2 steps)
- Move pointers until fast or fast.next is null (no cycle)
- If slow == fast at any point, cycle exists
- Returns true if cycle found, else false
- Efficient: O(n) time, O(1) space

Full Transcript

This visualization shows Floyd's cycle detection algorithm in a linked list. Two pointers start at the head. Slow moves one node at a time, fast moves two nodes. If the list has a cycle, fast will eventually catch slow inside the loop. The execution table traces each pointer move and checks if they meet. If they meet, the algorithm returns true indicating a cycle. If fast reaches the end (null), no cycle exists and returns false. Key moments clarify why we check fast and fast.next for null and how pointers meet. The quiz tests understanding of pointer positions and loop exit conditions.

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