Detect Cycle in Linked List Floyd's Algorithm in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floyd's Cycle Detection on a Linked List with a Cycle

What is the output of the following Java code that uses Floyd's algorithm to detect a cycle in a linked list?

DSA Java

class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

public class Test {
    public static boolean hasCycle(Node head) {
        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;
    }

    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);
        head.next.next.next.next = head.next; // cycle here
        System.out.println(hasCycle(head));
    }
}

A false

B true

C Compilation error

D Runtime exception

💡 Hint

Remember that Floyd's algorithm uses two pointers moving at different speeds to detect cycles.

The code creates a linked list with a cycle by pointing the last node back to the second node. Floyd's algorithm detects this cycle by moving slow pointer one step and fast pointer two steps. When they meet, it returns true.

❓ Predict Output

intermediate

Output of Floyd's Algorithm on a Linked List without a Cycle

What will the following Java code print when Floyd's algorithm is used on a linked list without any cycle?

DSA Java

class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

public class Test {
    public static boolean hasCycle(Node head) {
        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;
    }

    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);
        System.out.println(hasCycle(head));
    }
}

A false

B NullPointerException

C true

D Compilation error

💡 Hint

Think about what happens when the fast pointer reaches the end of the list.

Since the linked list has no cycle, the fast pointer will reach null and the function returns false.

🔧 Debug

advanced

Identify the Error in Floyd's Cycle Detection Implementation

What error will the following Java code produce when trying to detect a cycle using Floyd's algorithm?

DSA Java

class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

public class Test {
    public static boolean hasCycle(Node head) {
        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;
    }

    public static void main(String[] args) {
        Node head = null;
        System.out.println(hasCycle(head));
    }
}

A true

B Compilation error

C false

D NullPointerException

💡 Hint

Check the order of conditions in the while loop.

The code checks fast.next before checking if fast is null, which can cause NullPointerException if fast is null.

🧠 Conceptual

advanced

Why Does Floyd's Algorithm Use Two Pointers Moving at Different Speeds?

Why does Floyd's cycle detection algorithm use two pointers moving at different speeds (slow and fast) to detect a cycle in a linked list?

A Because the slow pointer can skip nodes to speed up detection.

B Because two pointers moving at the same speed can detect cycles faster.

C Because the fast pointer will eventually catch up to the slow pointer if there is a cycle.

D Because the fast pointer checks for null values while the slow pointer counts nodes.

💡 Hint

Think about what happens when two runners run on a circular track at different speeds.

If there is a cycle, the fast pointer moves faster and will eventually meet the slow pointer inside the cycle, confirming its presence.

🚀 Application

expert

Find the Starting Node of the Cycle Using Floyd's Algorithm

Given a linked list with a cycle, which code snippet correctly finds the node where the cycle begins using Floyd's algorithm?

DSA Java

class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

public class Test {
    public static Node detectCycleStart(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                Node start = head;
                while (start != slow) {
                    start = start.next;
                    slow = slow.next;
                }
                return start;
            }
        }
        return null;
    }

    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);
        head.next.next.next.next = head.next; // cycle starts at node with data 2
        Node cycleStart = detectCycleStart(head);
        System.out.println(cycleStart.data);
    }
}

A 2

B 3

C 4

D 1

💡 Hint

After detecting the cycle, reset one pointer to head and move both one step at a time until they meet.

After detecting the cycle, moving one pointer to head and advancing both pointers one step at a time leads them to meet at the cycle start node.

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