Definition
- Floyd's algorithm – the tortoise and hare: two pointers at different speeds detect and locate cycles in linked lists.
- Detection (phase 1) – slow moves one node, fast moves two; meeting means a cycle exists; fast reaching null means no cycle.
- Entry finding (phase 2) – reset one pointer to head, advance both by one; they meet at the cycle start.
- Space advantage – O(1) extra space versus O(n) for a hash set.
- Generality – the same technique works on any sequence defined by a function, not just linked lists.
The National Bank of India chains transaction records together, and a corrupted chain might loop back on itself, causing any traversal to run forever. A supervisor sends two auditors: a slow one stepping one record at a time and a fast one stepping two. If there is a loop, the fast auditor laps the slow one and they collide, proving the loop exists. To find where the loop starts, one auditor goes back to the beginning and both walk one step at a time until they meet.
Understanding the Concepts
What is Floyd's cycle detection and entry-finding algorithm?
Floyd's algorithm solves two problems in one: detecting whether a cycle exists and finding the exact node where the cycle begins. It uses two pointers moving at different speeds and requires only O(1) extra space. This is the complete solution that combines both phases.
package com.bank.model;
import java.math.BigDecimal;
public class TxnRecord {
public String txnId;
public BigDecimal amount;
public TxnRecord next;
public TxnRecord(String txnId, BigDecimal amount) {
this.txnId = txnId;
this.amount = amount;
}
}
How does phase one (detection) work?
Start both slow and fast at the head. Loop while fast and fast.next are not null. Each iteration, advance slow by one and fast by two. If slow == fast, a cycle exists.
package com.bank.service;
import com.bank.model.TxnRecord;
public class FloydCycleDetector {
public static TxnRecord detectCycleStart(TxnRecord head) {
TxnRecord slow = head;
TxnRecord fast = head;
// Phase 1: detect cycle
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// Phase 2: find entry
TxnRecord entry = head;
while (entry != slow) {
entry = entry.next;
slow = slow.next;
}
return entry; // cycle start node
}
}
return null; // no cycle
}
}
How does phase two (entry finding) work?
After detection, reset one pointer to the head and keep the other at the meeting point. Advance both by one step at a time. They meet at the cycle entry node.
package com.bank.service;
import com.bank.model.TxnRecord;
import java.math.BigDecimal;
public class FloydDemo {
public static void main(String[] args) {
TxnRecord a = new TxnRecord("TXN-A", new BigDecimal("1000"));
TxnRecord b = new TxnRecord("TXN-B", new BigDecimal("2000"));
TxnRecord c = new TxnRecord("TXN-C", new BigDecimal("3000"));
TxnRecord d = new TxnRecord("TXN-D", new BigDecimal("4000"));
TxnRecord e = new TxnRecord("TXN-E", new BigDecimal("5000"));
a.next = b; b.next = c; c.next = d; d.next = e;
e.next = c; // cycle back to C
TxnRecord start = FloydCycleDetector.detectCycleStart(a);
if (start != null) {
System.out.println("Cycle starts at: " + start.txnId);
} else {
System.out.println("No cycle");
}
}
}
Cycle starts at: TXN-C
Why are the pointers guaranteed to meet inside a cycle?
Once both pointers are inside the loop, the fast pointer gains one node on the slow pointer every step. The gap shrinks by one each iteration. If the gap is d, after d more steps it is zero and they collide. The gap cannot skip zero because it changes by exactly one.
Inside a cycle of length L: Step 0: gap = d Step 1: gap = d - 1 Step 2: gap = d - 2 ... Step d: gap = 0 → collision
Why does the phase-two walk find the entry?
Let a = distance from head to cycle start, b = distance from cycle start to meeting point, L = cycle length. Slow traveled a + b. Fast traveled 2(a + b). The difference a + b must be a multiple of L: a + b = nL, so a = nL - b. This means walking a steps from the head and a steps from the meeting point (which equals nL - b steps around the loop) both land on the cycle start.
// The math in action:
// a = distance from head to cycle start
// b = distance from cycle start to meeting point
// L = cycle length
// slow traveled: a + b
// fast traveled: 2(a + b)
// difference: a + b = multiple of L
// therefore: a = nL - b
// walking a from head AND a from meeting → both reach cycle start
How is this different from the hash-set approach?
The hash-set approach stores every visited node and returns the first repeat. It detects and finds the cycle start in one pass but uses O(n) space. Floyd's uses O(1) space but requires the mathematical insight.
| Feature | Floyd's Algorithm | Hash-Set |
|---|---|---|
| Time | O(n) | O(n) |
| Space | O(1) | O(n) |
| Detects cycle | Yes | Yes |
| Finds start | Yes (phase 2) | Yes (first repeat) |
| Understanding | Requires math proof | Straightforward |
What are the edge cases?
Empty list, single node no cycle, single node self-loop, cycle starting at head, and very long tail with short cycle.
package com.bank.service;
import com.bank.model.TxnRecord;
import java.math.BigDecimal;
public class FloydEdgeCases {
public static void main(String[] args) {
// Empty
System.out.println("Empty: " + FloydCycleDetector.detectCycleStart(null));
// Single node, no cycle
TxnRecord single = new TxnRecord("T1", new BigDecimal("100"));
System.out.println("Single no cycle: " + FloydCycleDetector.detectCycleStart(single));
// Single node, self-loop
single.next = single;
System.out.println("Self-loop: " + FloydCycleDetector.detectCycleStart(single).txnId);
}
}
Empty: null
Single no cycle: null
Self-loop: T1
What about applications beyond linked lists?
The tortoise-and-hare principle applies to any sequence x, f(x), f(f(x)), ... where f is a function. If the sequence enters a cycle, Floyd's detects it. The classic "find the duplicate number" problem models array values as function outputs: f(i) = nums[i], and a duplicate creates a cycle.
public static int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
int entry = nums[0];
while (entry != slow) {
entry = nums[entry];
slow = nums[slow];
}
return entry;
}
What should a senior engineer know?
A senior engineer should be able to derive the phase-two proof from scratch. The key equation a + b = nL comes from the fact that fast travels twice as far as slow, and any extra distance must be whole loops. From there, a = nL - b immediately justifies the reset-and-walk technique.
In production at National Bank of India, Floyd's algorithm runs as a validation step before processing imported transaction chains, detecting and locating corrupt loop-backs in O(1) space.
public static void validateAndRepair(TxnRecord head) {
TxnRecord cycleStart = FloydCycleDetector.detectCycleStart(head);
if (cycleStart != null) {
// Find the node before the cycle start and break the link
TxnRecord runner = cycleStart;
while (runner.next != cycleStart) runner = runner.next;
runner.next = null;
System.out.println("Repaired cycle at " + cycleStart.txnId);
}
}
Visual Overview
Phase 1: Detection
head ──> [A] ──> [B] ──> [C] ──> [D] ──> [E]
▲ │
└───────────────┘
slow: A → B → C → D → E → C → D
fast: A → C → E → D → C → E → D
Meet at D (inside the cycle)
Phase 2: Entry Finding
entry = head = A slow = D (meeting point)
A → B D → E → C
B → C C (arrived)
They meet at C = cycle start!
Distance Proof
head ──a──> [start] ──b──> [meet]
▲ │
└───(L-b)───────┘
slow: a + b steps
fast: 2(a + b) steps
fast - slow = a + b = nL
therefore a = nL - b
Walk a from head + Walk a from meet → both reach start
Key Takeaway
Floyd's cycle-detection algorithm, the tortoise and hare, solves two problems in one: detecting whether a cycle exists and finding the exact node where it begins. Phase one moves slow by one and fast by two; if they meet, a cycle exists. Phase two resets one pointer to the head and walks both by one; they meet at the cycle's entry node. The entire algorithm runs in O(n) time and O(1) space.
The mathematical justification for phase two is short and elegant. Slow travels a + b steps, fast travels 2(a + b), and the difference a + b must be a full number of loop lengths. Therefore a = nL - b, which means walking a steps from the head and a steps from the meeting point both land on the cycle start. A senior engineer should be able to derive this on a whiteboard rather than just recite it.
The same tortoise-and-hare principle applies to any functional sequence, not just linked lists. The "find the duplicate number" problem treats array indices as links and uses Floyd's algorithm to find the duplicate in O(1) space. Recognizing this broader applicability unlocks a family of cycle-related problems.
In our banking system at National Bank of India, Floyd's algorithm validates imported transaction chains before processing. A corrupt import can loop a chain back on itself, and the algorithm detects the loop and locates the entry node so the repair tool can cut the bad link, all in constant extra space.
Remember one sentence: slow by one, fast by two to detect; reset one to head, walk both by one to find the cycle start, because a = nL - b.
---