Definition
- Floyd's algorithm – also called the tortoise and hare; uses two pointers at different speeds to detect a cycle in a linked list.
- Slow pointer – advances one node per step.
- Fast pointer – advances two nodes per step.
- Cycle detected – when
slow == fast(same node reference), a cycle exists. - No cycle – when
fastorfast.nextbecomesnull, the list ends and there is no cycle. - Complexity – O(n) time, O(1) space.
The National Bank of India links transaction records in a chain, and a corrupted import could accidentally point a record back into the chain, forming an endless loop that would hang any traversal. A supervisor sends two auditors down the chain: a slow one stepping one record at a time and a fast one stepping two at a time. If the chain simply ends, the fast auditor falls off the end. But if the chain loops, the fast auditor keeps circling and inevitably catches up to the slow one, proving a loop exists.
Understanding the Concepts
What is cycle detection in a linked list?
A cycle in a linked list occurs when a node's next pointer points back to a previous node in the chain, creating an infinite loop. Any naive traversal that follows next pointers until null will run forever if a cycle exists. Floyd's cycle detection algorithm, also called the tortoise and hare, determines whether a linked list contains a cycle using two pointers and no extra memory.
package com.bank.model;
import java.math.BigDecimal;
public class TransactionNode {
public String txnId;
public BigDecimal amount;
public TransactionNode next;
public TransactionNode(String txnId, BigDecimal amount) {
this.txnId = txnId;
this.amount = amount;
this.next = null;
}
}
How does Floyd's algorithm work?
Start both slow and fast at the head. Loop while fast != null && fast.next != null. Each iteration, advance slow by one node and fast by two nodes. After each move, compare the two pointers. If slow == fast, a cycle exists. If the loop exits because fast became null, the list is acyclic.
package com.bank.service;
import com.bank.model.TransactionNode;
public class CycleDetector {
public static boolean hasCycle(TransactionNode head) {
TransactionNode slow = head;
TransactionNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true; // cycle detected
}
}
return false; // no cycle
}
}
Why are the two pointers guaranteed to meet inside a cycle?
Once both pointers enter the cycle, the fast pointer gains exactly one node on the slow pointer every step. Think of it as the gap between them shrinking by one each iteration. If the gap is currently d nodes, after d more steps the gap is zero and they collide. They cannot jump past each other because the gap changes by exactly one per step.
package com.bank.service;
import com.bank.model.TransactionNode;
import java.math.BigDecimal;
public class CycleMeetingProof {
public static void main(String[] args) {
// Build chain: TXN-001 -> TXN-002 -> TXN-003 -> TXN-004 -> back to TXN-002
TransactionNode n1 = new TransactionNode("TXN-001", new BigDecimal("1000"));
TransactionNode n2 = new TransactionNode("TXN-002", new BigDecimal("2000"));
TransactionNode n3 = new TransactionNode("TXN-003", new BigDecimal("3000"));
TransactionNode n4 = new TransactionNode("TXN-004", new BigDecimal("4000"));
n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2; // cycle!
TransactionNode slow = n1, fast = n1;
int step = 0;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
step++;
System.out.println("Step " + step + ": slow=" + slow.txnId + " fast=" + fast.txnId);
if (slow == fast) {
System.out.println("Met at " + slow.txnId + " after " + step + " steps");
break;
}
}
}
}
Step 1: slow=TXN-002 fast=TXN-003
Step 2: slow=TXN-003 fast=TXN-003
Met at TXN-003 after 2 steps
How is this different from the hash-set approach?
The hash-set approach stores every visited node in a HashSet and checks for repeats. It also detects cycles in O(n) time but uses O(n) space. Floyd's algorithm achieves the same result in O(1) space.
| Feature | Floyd's Algorithm | Hash-Set Approach |
|---|---|---|
| Time | O(n) | O(n) |
| Space | O(1) | O(n) |
| Finds cycle start | Needs second phase | Immediately (first repeat) |
| Code complexity | Simple two-pointer | Requires set operations |
import java.util.HashSet;
import java.util.Set;
// Hash-set approach: O(n) time, O(n) space
public static boolean hasCycleHashSet(TransactionNode head) {
Set<TransactionNode> visited = new HashSet<>();
TransactionNode current = head;
while (current != null) {
if (!visited.add(current)) {
return true; // already visited this node
}
current = current.next;
}
return false;
}
Why must the comparison be reference equality?
The comparison slow == fast checks whether both pointers reference the same node object, not whether the values are equal. Two different nodes can hold the same value, and comparing values would produce a false positive. Cycle detection is a structural check, not a value check.
// WRONG: value comparison gives false positive on duplicate values
if (slow.amount.equals(fast.amount)) { ... } // not a cycle!
// CORRECT: reference comparison detects structural loop
if (slow == fast) { ... } // same node object
What are the edge cases?
The main edge cases are an empty list, a single node with no cycle, and a single node that points to itself.
package com.bank.service;
import com.bank.model.TransactionNode;
import java.math.BigDecimal;
public class CycleEdgeCases {
public static void main(String[] args) {
// Empty list
System.out.println("Empty: " + CycleDetector.hasCycle(null));
// Single node, no cycle
TransactionNode single = new TransactionNode("TXN-001", new BigDecimal("1000"));
System.out.println("Single no cycle: " + CycleDetector.hasCycle(single));
// Single node pointing to itself
single.next = single;
System.out.println("Single self-cycle: " + CycleDetector.hasCycle(single));
}
}
Empty: false
Single no cycle: false
Single self-cycle: true
What about the fast pointer guard condition?
The guard fast != null && fast.next != null is essential because the fast pointer reads two links ahead. If you only check fast != null, then fast.next.next could throw a NullPointerException when fast.next is null. The double guard ensures both steps are safe.
// Guard explained:
// fast != null -> fast itself exists
// fast.next != null -> fast can safely do fast.next.next
while (fast != null && fast.next != null) {
slow = slow.next; // one step
fast = fast.next.next; // two steps, safe because of guard
}
What should a senior engineer know?
Floyd's algorithm is the foundation for several related problems. The next step after detection is finding the cycle start node, which uses a second phase where one pointer resets to the head and both advance one step at a time until they meet at the entry point. The same tortoise-and-hare principle applies to detecting cycles in any sequence defined by a function, such as the "find the duplicate number" problem where array indices are treated as links.
In production at the National Bank of India, cycle detection prevents infinite traversal in transaction chains built from imported data. A corrupted import can create a loop, and the cycle detector runs as a validation step before processing begins.
package com.bank.service;
import com.bank.model.TransactionNode;
public class ChainValidator {
public static void validateChain(TransactionNode head) {
if (CycleDetector.hasCycle(head)) {
throw new IllegalStateException(
"Corrupted transaction chain detected: cycle found. "
+ "Import rejected for manual review."
);
}
}
}
Visual Overview
Floyd's Tortoise and Hare
No Cycle Case:
head ──> [A] ──> [B] ──> [C] ──> null
s f fast hits null
s f → no cycle
Cycle Case:
head ──> [A] ──> [B] ──> [C] ──> [D]
▲ │
└───────────────┘
Step 1: slow=B, fast=C
Step 2: slow=C, fast=C → met! cycle exists
Why They Must Meet (gap shrinks by 1 each step) Inside cycle of length L: ┌──> [B] ──> [C] ──> [D] ──┐ │ │ └───────────────────────────┘ Step 0: gap = d Step 1: gap = d - 1 (fast gains 1) Step 2: gap = d - 2 .... Step d: gap = 0 → collision!
Key Takeaway
Floyd's cycle detection algorithm, the tortoise and hare, determines whether a linked list has a loop using two pointers and no extra memory. You start a slow pointer and a fast pointer at the head, advance slow by one node and fast by two nodes each step, and check whether they ever reference the same node. If they meet, a cycle exists. If the fast pointer reaches the end of the list, there is no cycle.
The reason the meeting is guaranteed when a cycle exists is a clean argument. Once both pointers are inside the loop, the fast pointer closes the gap to the slow pointer by exactly one node every step. The gap shrinks by one each iteration until it reaches zero, and because the change is exactly one, the fast pointer cannot leap over the slow pointer without landing on it.
Two details matter for correctness. First, the comparison must be reference equality (==), not value equality, because two different nodes with the same value do not constitute a cycle. Second, the guard condition fast != null && fast.next != null must check both, because the fast pointer reads two links ahead and skipping the second check risks a NullPointerException.
In our banking system at National Bank of India, we use Floyd's algorithm as a validation step before processing imported transaction chains. A corrupted import can accidentally point a later record back to an earlier one, creating a loop that would make the processor run forever. The cycle detector catches this in O(n) time with O(1) space, and because memory is constrained in the import pipeline, the constant-space method is preferred over a visited hash set.
Remember one sentence: slow by one, fast by two; if they meet there is a cycle, if fast hits null there is not.
---