Detect Cycle in Linked List Floyd's Algorithm in DSA Java - Deep Dive

Overview - Detect Cycle in Linked List Floyd's Algorithm

What is it?

Detecting a cycle in a linked list means finding out if the list loops back on itself instead of ending with a null. Floyd's Algorithm, also called the Tortoise and Hare method, uses two pointers moving at different speeds to find this loop. If the fast pointer catches up to the slow pointer, a cycle exists. This helps avoid infinite loops when processing linked lists.

Why it matters

Without detecting cycles, programs can get stuck forever when traversing linked lists that loop. This can cause crashes or freezes in software. Floyd's Algorithm provides a simple and efficient way to find cycles without extra memory. It ensures programs handle linked lists safely and correctly, which is crucial in many applications like networking, memory management, and data processing.

Where it fits

Before learning this, you should understand what linked lists are and how to traverse them. After this, you can learn about removing cycles, finding the start of the cycle, and other linked list problems like reversing or merging. This topic fits into the broader study of pointers, references, and efficient algorithms for data structures.

Mental Model

Core Idea

If two pointers move through a linked list at different speeds, they will meet inside a cycle if one exists.

Think of it like...

Imagine two runners on a circular track: one runs slowly, the other runs faster. If the track loops, the faster runner will eventually catch up to the slower one.

Linked List with cycle:

Head -> [1] -> [2] -> [3] -> [4] -> [5]
                      ^                   |
                      |-------------------|

Pointers:
Slow: moves one step at a time
Fast: moves two steps at a time

If cycle exists, fast pointer will lap slow pointer inside the loop.

Build-Up - 7 Steps

1

Foundation

Understanding Linked List Basics

Concept: Learn what a linked list is and how nodes connect with pointers.

A linked list is a chain of nodes where each node holds data and a reference to the next node. The last node points to null, meaning the list ends there. Traversing means moving from one node to the next until null is reached.

Result

You can follow nodes one by one from the start to the end of the list.

Understanding how nodes link is essential before detecting cycles, as cycles break the normal end condition.

2

Foundation

What is a Cycle in Linked List?

Concept: A cycle means the list loops back to an earlier node instead of ending.

In a cycle, a node's next pointer points to a previous node, creating a loop. This means traversing the list never reaches null and can go on forever.

Result

Traversal without cycle detection can cause infinite loops.

Recognizing the problem of cycles explains why special detection methods like Floyd's Algorithm are needed.

3

Intermediate

Two Pointer Technique Introduction

Concept: Use two pointers moving at different speeds to detect cycles.

Initialize two pointers at the head. Move the slow pointer one step at a time and the fast pointer two steps at a time. If the fast pointer reaches null, no cycle exists. If the fast pointer meets the slow pointer, a cycle exists.

Result

Cycle detection is done in O(n) time without extra memory.

Using two pointers with different speeds cleverly exploits the cycle's loop structure to detect it efficiently.

4

Intermediate

Dry Run of Floyd's Algorithm

🤔Before reading on: do you think the fast pointer will meet the slow pointer if there is a cycle? Commit to yes or no.

Concept: Step through the algorithm to see how pointers move and meet inside a cycle.

Example list with cycle: 1->2->3->4->5->3... - Start: slow=1, fast=1 - Move 1: slow=2, fast=3 - Move 2: slow=3, fast=5 - Move 3: slow=4, fast=4 (fast caught slow) Pointers meet, cycle detected.

Result

Pointers meet inside the cycle confirming its presence.

Seeing the pointers meet in a real example builds intuition on why the algorithm works.

5

Intermediate

Implementing Floyd's Algorithm in Java

Concept: Write code to detect cycle using two pointers.

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

Result

The method returns true if a cycle exists, false otherwise.

Implementing the algorithm solidifies understanding and shows how simple the code can be.

6

Advanced

Finding Cycle Start Node

🤔Before reading on: do you think the meeting point of pointers is the start of the cycle? Commit to yes or no.

Concept: After detecting a cycle, find the exact node where the cycle begins.

Once slow and fast meet, reset slow to head. Move both pointers one step at a time. The node where they meet again is the cycle start. Why? Because the distance from head to cycle start equals the distance from meeting point to cycle start inside the loop.

Result

You can identify the node where the cycle begins.

Knowing how to find the cycle start helps in removing cycles or understanding list structure.

7

Expert

Algorithm Limitations and Variations

🤔Before reading on: do you think Floyd's Algorithm works for all cycle detection problems? Commit to yes or no.

Concept: Explore cases where Floyd's Algorithm may not be ideal and alternative methods.

Floyd's Algorithm assumes singly linked lists with next pointers. It doesn't detect cycles in structures without clear next references or in graphs. Alternatives like hashing visited nodes use extra memory but work in more general cases. Also, Floyd's Algorithm doesn't tell cycle length directly without extra steps.

Result

Understanding when to use or avoid Floyd's Algorithm improves algorithm choice.

Knowing the algorithm's boundaries prevents misuse and guides choosing the right tool for complex problems.

Under the Hood

Floyd's Algorithm uses two pointers moving at different speeds. If a cycle exists, the fast pointer laps the slow pointer inside the loop. This happens because the fast pointer moves two steps while the slow moves one, so the distance between them decreases by one each step inside the cycle until they meet.

Why designed this way?

The algorithm was designed to detect cycles efficiently without extra memory. Previous methods used hash sets to track visited nodes, which require extra space. Floyd's method cleverly uses pointer speed difference to detect cycles in linear time and constant space.

Start
  ↓
[Head]
  ↓
Slow pointer -> moves 1 step
Fast pointer -> moves 2 steps

Cycle loop:
┌─────────────┐
│             │
│  [Cycle]    │
│             │
└─────────────┘

Inside cycle:
Distance between pointers decreases by 1 each step until they meet.

Myth Busters - 3 Common Misconceptions

Quick: Does the meeting point of slow and fast pointers always mark the cycle's start? Commit yes or no.

Common Belief: The point where slow and fast pointers meet is the start of the cycle.

Reality: The meeting point is somewhere inside the cycle but not necessarily the start. To find the start, you must reset one pointer and move both at the same speed until they meet again.

Why it matters: Assuming the meeting point is the start leads to incorrect cycle removal or misunderstanding of the list structure.

Quick: Can Floyd's Algorithm detect cycles in any data structure? Commit yes or no.

Common Belief: Floyd's Algorithm works for all cycle detection problems.

Reality: It only works for singly linked lists with next pointers. It cannot detect cycles in graphs or other structures without linear next references.

Why it matters: Using Floyd's Algorithm outside its scope leads to wrong results or infinite loops.

Quick: Does Floyd's Algorithm require extra memory to detect cycles? Commit yes or no.

Common Belief: Cycle detection requires extra memory like hash sets to track visited nodes.

Reality: Floyd's Algorithm detects cycles using only two pointers and constant extra space.

Why it matters: Knowing this helps write memory-efficient code and choose Floyd's Algorithm for large data.

Expert Zone

1

The distance between slow and fast pointers inside the cycle decreases by exactly one each step, guaranteeing a meeting point.

2

Resetting slow pointer to head after detection and moving both pointers at the same speed leverages the mathematical relationship between distances traveled to find the cycle start.

3

Floyd's Algorithm can be extended to find cycle length by counting steps after pointers meet.

When NOT to use

Avoid Floyd's Algorithm for cycle detection in graphs or doubly linked lists with complex back pointers. Use hash-based detection or coloring methods instead. Also, if you need to know cycle length or all cycle nodes immediately, other algorithms may be more direct.

Production Patterns

Floyd's Algorithm is widely used in memory management to detect infinite loops in pointer chains, in network routing to detect loops, and in interview coding tests as a standard cycle detection method due to its efficiency and simplicity.

Connections

Graph Cycle Detection

Builds-on

Understanding cycle detection in linked lists helps grasp more complex cycle detection in graphs, which often requires different algorithms like DFS with visited sets.

Race Conditions in Concurrency

Opposite pattern

Floyd's Algorithm uses two pointers moving at different speeds to detect cycles, while race conditions involve multiple threads racing unpredictably; understanding controlled pointer movement aids in reasoning about concurrency timing.

Circular Motion in Physics

Same pattern

The idea of one object moving faster on a circular path catching up to a slower one mirrors the pointers in Floyd's Algorithm, showing how physical motion concepts apply to algorithm design.

Common Pitfalls

#1 Not checking for null before moving fast pointer.

Wrong approach:

while (fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}

Correct approach:

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}

Root cause:

Failing to check fast for null causes runtime errors when fast reaches the list end.

#2 Assuming meeting point is cycle start and removing cycle incorrectly.

Wrong approach:

if (slow == fast) {
slow.next = null; // breaks cycle at meeting point
}

Correct approach:

if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
slow.next = null; // removes cycle at start
}

Root cause:

Misunderstanding that meeting point is inside cycle, not start, leads to incorrect cycle removal.

Key Takeaways

Floyd's Algorithm detects cycles in linked lists by using two pointers moving at different speeds.

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

The meeting point is not necessarily the start of the cycle; resetting one pointer helps find the cycle's start node.

This algorithm works in linear time and constant space, making it efficient and practical.

Understanding its limits and correct implementation prevents common bugs and misuse.

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