Definition
- Floyd's tortoise and hare – a cycle detection algorithm using two pointers: slow moves one node per step, fast moves two nodes per step.
- Meeting guarantees cycle – in a cycle, the fast pointer gains one node on the slow each step, so the gap closes to zero and they meet.
- Null guarantees no cycle – if the fast pointer or its next reaches null, the list has a genuine end and no cycle.
- Constant space – only two pointer variables are needed, unlike the HashSet approach which uses O(n) space.
- Relative speed argument – inside a cycle of length C, the fast pointer closes the gap by 1 each step, so they meet within C steps.
Rajesh follows a chain of linked transaction records at National Bank of India, where each record points to the next. A corruption bug can make a record point back to an earlier one, creating an endless loop. He sends two readers: a slow one moving one record at a time and a fast one moving two. If the chain loops, the fast reader catches up to the slow one. If it hits the end, the chain is clean.
Understanding the Concepts
What is the Linked List Cycle problem?
The problem gives the head of a singly linked list and asks whether any node's next pointer points back to an earlier node, creating a cycle. The solution must use constant extra space. This is the classic application of Floyd's tortoise and hare algorithm.
package com.bank.service;
public class LinkedListCycle {
static class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // one step
fast = fast.next.next; // two steps
if (slow == fast) return true; // met inside cycle
}
return false; // fast reached the end
}
public static void main(String[] args) {
// Build: T1 -> T2 -> T3 -> T4 -> T2 (cycle)
ListNode t1 = new ListNode(1);
ListNode t2 = new ListNode(2);
ListNode t3 = new ListNode(3);
ListNode t4 = new ListNode(4);
t1.next = t2; t2.next = t3; t3.next = t4; t4.next = t2;
System.out.println("Has cycle: " + new LinkedListCycle().hasCycle(t1));
}
}
Has cycle: true
Why does Floyd's algorithm work?
The key is the relative speed argument. Once both pointers are inside the cycle, the fast pointer gains exactly one node on the slow pointer each step. If the cycle has length C, the gap between them decreases by 1 each step, so within C steps the gap becomes zero and they land on the same node. The fast pointer cannot skip over the slow pointer because the gap changes by exactly 1.
package com.bank.service;
public class RelativeSpeedProof {
// Suppose slow is at position s, fast at position f in the cycle
// gap = (f - s) mod C
// Each step: slow moves 1, fast moves 2
// New gap = (f+2 - s-1) mod C = gap + 1 mod C
// But relative to slow, fast advances 1 per step
// So gap decreases by 1 each step (from slow's perspective)
// After C steps, gap = 0 => they meet
public static void main(String[] args) {
System.out.println("Fast gains 1 node per step on slow.");
System.out.println("In a cycle of length C, they meet within C steps.");
System.out.println("Fast cannot skip slow: gap changes by exactly 1.");
}
}
How is this different from the HashSet approach?
| Feature | Floyd's fast/slow | HashSet approach |
|---|---|---|
| Space | O(1) constant | O(n) for storing all seen nodes |
| Time | O(n) | O(n) |
| Extra data | two pointers | HashSet of node references |
| Finds cycle start | yes (with phase 2) | yes (first repeated node) |
| Preferred when | constant space required | need to identify cycle nodes |
package com.bank.service;
import java.util.HashSet;
import java.util.Set;
public class CycleHashSet {
public boolean hasCycle(LinkedListCycle.ListNode head) {
Set<LinkedListCycle.ListNode> seen = new HashSet<>();
LinkedListCycle.ListNode current = head;
while (current != null) {
if (!seen.add(current)) return true; // already seen
current = current.next;
}
return false;
}
public static void main(String[] args) {
LinkedListCycle.ListNode t1 = new LinkedListCycle.ListNode(1);
LinkedListCycle.ListNode t2 = new LinkedListCycle.ListNode(2);
t1.next = t2; t2.next = t1;
System.out.println("Has cycle (HashSet): " + new CycleHashSet().hasCycle(t1));
}
}
Has cycle (HashSet): true
What are the rules for the null safety check?
Before advancing the fast pointer two steps, check that both fast and fast.next are non-null. If either is null, the list has a genuine end and there is no cycle. On an even-length acyclic list, fast itself may be null. On an odd-length acyclic list, fast.next may be null. Checking both covers all cases.
package com.bank.service;
public class NullSafetyCheck {
// while (fast != null && fast.next != null)
// fast != null: catches even-length end (fast lands on null)
// fast.next != null: catches odd-length end (fast.next is null)
public static void main(String[] args) {
// Even length: 1 -> 2 -> null
// fast starts at 1, moves to null (even case)
LinkedListCycle.ListNode n1 = new LinkedListCycle.ListNode(1);
LinkedListCycle.ListNode n2 = new LinkedListCycle.ListNode(2);
n1.next = n2;
System.out.println("Even length: " + new LinkedListCycle().hasCycle(n1));
// Odd length: 1 -> 2 -> 3 -> null
LinkedListCycle.ListNode n3 = new LinkedListCycle.ListNode(3);
n2.next = n3;
System.out.println("Odd length: " + new LinkedListCycle().hasCycle(n1));
}
}
Even length: false
Odd length: false
How do you find the start of the cycle?
After detecting a meeting point, reset one pointer to the head and keep the other at the meeting point. Advance both one step at a time. They will meet at the cycle start. This works because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (within the cycle).
package com.bank.service;
public class CycleStart {
public LinkedListCycle.ListNode detectCycleStart(LinkedListCycle.ListNode head) {
LinkedListCycle.ListNode slow = head, fast = head;
// Phase 1: detect meeting point
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
if (fast == null || fast.next == null) return null; // no cycle
// Phase 2: find cycle start
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // cycle start
}
public static void main(String[] args) {
LinkedListCycle.ListNode n1 = new LinkedListCycle.ListNode(1);
LinkedListCycle.ListNode n2 = new LinkedListCycle.ListNode(2);
LinkedListCycle.ListNode n3 = new LinkedListCycle.ListNode(3);
LinkedListCycle.ListNode n4 = new LinkedListCycle.ListNode(4);
n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2;
LinkedListCycle.ListNode start = new CycleStart().detectCycleStart(n1);
System.out.println("Cycle starts at node: " + (start != null ? start.val : "none"));
}
}
Cycle starts at node: 2
What are the edge cases?
Edge cases include an empty list (null head), a single node with no cycle, a single node pointing to itself, and a cycle involving all nodes.
package com.bank.service;
public class CycleEdgeCases {
public static void main(String[] args) {
LinkedListCycle solver = new LinkedListCycle();
// Empty list
System.out.println("Empty: " + solver.hasCycle(null));
// Single node, no cycle
LinkedListCycle.ListNode single = new LinkedListCycle.ListNode(1);
System.out.println("Single no cycle: " + solver.hasCycle(single));
// Single node, self-loop
single.next = single;
System.out.println("Self-loop: " + solver.hasCycle(single));
}
}
Empty: false
Single no cycle: false
Self-loop: true
What are common mistakes?
The most common mistake is checking only fast != null without also checking fast.next != null, which causes a NullPointerException when advancing two steps on an odd-length list. Another mistake is comparing node values instead of node references, which would falsely detect a cycle when two different nodes have the same value.
Wrong code:
// WRONG: missing fast.next null check
while (fast != null) { // should also check fast.next
slow = slow.next;
fast = fast.next.next; // NullPointerException on odd-length list
}
Correct code:
// CORRECT: check both fast and fast.next
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
What should a senior engineer know?
A senior engineer knows that Floyd's algorithm extends to finding the cycle start (phase 2) and computing the cycle length. They also know the mathematical proof: if the tail length is mu and the cycle length is C, at the meeting point the slow pointer has traveled mu + k steps inside the cycle, and resetting one pointer to the head and advancing both by one gives the cycle start in mu steps. In production at National Bank of India, the integrity checker uses this to detect circular references in linked transaction chains on memory-constrained infrastructure.
package com.bank.service;
public class SeniorCycleNotes {
// Cycle length: after meeting, keep one pointer fixed, advance the other
// counting steps until they meet again. Count = cycle length.
public static int cycleLength(LinkedListCycle.ListNode meetingPoint) {
LinkedListCycle.ListNode current = meetingPoint.next;
int length = 1;
while (current != meetingPoint) {
current = current.next;
length++;
}
return length;
}
public static void main(String[] args) {
LinkedListCycle.ListNode n1 = new LinkedListCycle.ListNode(1);
LinkedListCycle.ListNode n2 = new LinkedListCycle.ListNode(2);
LinkedListCycle.ListNode n3 = new LinkedListCycle.ListNode(3);
n1.next = n2; n2.next = n3; n3.next = n2; // cycle of length 2
// Find meeting point first
System.out.println("Cycle length: " + cycleLength(n2));
}
}
Cycle length: 2
Visual Overview
Floyd's Tortoise and Hare
List: T1 -> T2 -> T3 -> T4 -> T2 (cycle)
Step 0: slow=T1 fast=T1
Step 1: slow=T2 fast=T3 (slow+1, fast+2)
Step 2: slow=T3 fast=T2 (slow+1, fast+2 through cycle)
Step 3: slow=T4 fast=T4 MEET! => cycle exists
Acyclic list: T1 -> T2 -> T3 -> null
Step 0: slow=T1 fast=T1
Step 1: slow=T2 fast=T3
Step 2: fast.next = null => STOP, no cycle
Finding Cycle Start (Phase 2):
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ T1 │──▶│ T2 │──▶│ T3 │──▶│ T4 │──┐
└────┘ └──▲─┘ └────┘ └────┘ │
│ │
└────────────────────────┘
After meeting at T4:
Reset slow to T1, keep fast at T4
Both move 1 step: slow=T2, fast=T2 => MEET at cycle start!
Key Takeaway
Detecting a cycle in a singly linked list is the classic use of Floyd's tortoise and hare algorithm. The slow pointer moves one node per step and the fast pointer moves two. If they meet, the list has a cycle. If the fast pointer reaches null, the list is acyclic. This runs in O(n) time with O(1) space, which is the key advantage over the HashSet approach that uses O(n) space.
The null safety check must verify both fast != null and fast.next != null before advancing two steps. Missing the fast.next check causes a NullPointerException on odd-length acyclic lists. The meeting guarantee comes from the relative speed: inside a cycle, the fast pointer closes the gap by exactly one node each step, so they must meet within one cycle length.
The algorithm extends naturally to finding where the cycle starts (reset one pointer to head, advance both by one until they meet) and computing the cycle length (from the meeting point, advance one pointer until it returns to the meeting point). These are common follow-up questions.
At National Bank of India, Rajesh used this in an integrity checker for linked transaction chains. A rare corruption bug could make a record point back to an earlier one, creating an infinite loop that would hang any downstream process. The chains were large and the checker ran on memory-constrained infrastructure, so the two-pointer method detected corruption in constant space before processing.
Remember one sentence: slow moves one step, fast moves two; meeting means a cycle, reaching null means no cycle, and it takes only O(1) space.
---