Detect Cycle in Linked List Floyd's Algorithm in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the slow pointer at the head of the linked list.

DSA Java

ListNode slow = [1];

Drag options to blanks, or click blank then click option'

Anull

Bfast

Cslow

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing slow to null causes no traversal.

Using fast instead of head mixes pointer roles.

The slow pointer must start at the head of the linked list to begin traversal.

2fill in blank

medium

Complete the code to move the fast pointer two steps ahead safely.

DSA Java

fast = fast != null && fast.next != null ? fast.next.[1] : null;

Drag options to blanks, or click blank then click option'

Aprev

Bnext

Chead

Dslow

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' which does not exist in singly linked list.

Using 'head' or 'slow' which are unrelated here.

To move fast pointer two steps, first move to next, then again to next.

3fill in blank

hard

Fix the error in the loop condition to avoid null pointer exceptions.

DSA Java

while (fast != null && fast.next != null && [1] != null) {

Drag options to blanks, or click blank then click option'

Aslow

Bfast

Chead

Dfast.next

Attempts:

3 left

💡 Hint

Common Mistakes

Not checking slow for null can cause errors.

Checking fast.next twice is redundant.

The slow pointer must be checked for null to safely move forward.

4fill in blank

hard

Fill both blanks to correctly move slow and fast pointers inside the loop.

DSA Java

slow = slow.[1];
fast = fast.[2].next;

Drag options to blanks, or click blank then click option'

Anext

Bprev

Chead

Dslow

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' which is not in singly linked list.

Using 'head' or 'slow' as properties causes errors.

Both slow and fast pointers move forward using the 'next' property.

5fill in blank

hard

Fill all three blanks to return true if cycle detected, else false after loop.

DSA Java

if (slow == [1]) {
    return [2];
}
return [3];

Drag options to blanks, or click blank then click option'

Afast

Btrue

Cfalse

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Returning head or wrong boolean values.

Comparing slow with head instead of fast.

If slow and fast meet, cycle exists so return true; else return false.

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