Definition
- Phase one – Floyd's detection: slow moves one step, fast moves two steps; if they meet, a cycle exists.
- Phase two – reset one pointer to the head, keep the other at the meeting point, advance both by one step; they meet at the cycle entry node.
- Why it works – the distance from head to cycle start equals the distance from meeting point to cycle start (modulo loop length), a consequence of the two-to-one speed ratio.
- Complexity – O(n) time, O(1) space.
- No cycle – if
fastreaches null in phase one, return null immediately.
The National Bank of India discovers that a transaction chain has a loop, but needs to find exactly which record the loop re-enters so the repair tool can cut the bad link. Rajesh first catches two fingers inside the loop (phase one), then moves one finger back to the start of the chain and walks both fingers one step at a time. The spot where they meet again is where the loop begins, and that is the link to cut.
Understanding the Concepts
What is Linked List Cycle II?
Linked List Cycle II goes beyond detecting a cycle. It finds the exact node where the cycle begins, which is the node that has two incoming references: one from the tail of the non-cyclic portion and one from inside the loop. Knowing this node allows you to break the cycle by setting the appropriate next pointer to null.
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;
}
}
How does phase one work?
Phase one is standard Floyd's detection. Start slow and fast at the head. Advance slow by one and fast by two. If they meet, a cycle exists and the meeting point is inside the loop. If fast reaches null, there is no cycle.
package com.bank.service;
import com.bank.model.TransactionNode;
public class CycleStartFinder {
public static TransactionNode findCycleStart(TransactionNode head) {
TransactionNode slow = head;
TransactionNode 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 point
TransactionNode entry = head;
while (entry != slow) {
entry = entry.next;
slow = slow.next;
}
return entry;
}
}
return null; // no cycle
}
}
Why does phase two find the cycle start?
Let a be the distance from head to the cycle start, and let b be the distance from the cycle start to the meeting point. The slow pointer has traveled a + b steps. The fast pointer has traveled 2(a + b) steps. Because the fast pointer also completed some full loops of length L inside the cycle:
2(a + b) = a + b + n * L for some integer n, which simplifies to a + b = n * L, and therefore a = n * L - b.
This means the distance from the head to the cycle start (a) equals the distance from the meeting point to the cycle start when measured forward around the loop (n * L - b). So two pointers starting from the head and the meeting point, both advancing one step at a time, will meet at the cycle start.
package com.bank.service;
import com.bank.model.TransactionNode;
import java.math.BigDecimal;
public class CycleStartDemo {
public static void main(String[] args) {
// Build: A -> B -> C -> D -> E -> back to C
TransactionNode a = new TransactionNode("TXN-A", new BigDecimal("1000"));
TransactionNode b = new TransactionNode("TXN-B", new BigDecimal("2000"));
TransactionNode c = new TransactionNode("TXN-C", new BigDecimal("3000"));
TransactionNode d = new TransactionNode("TXN-D", new BigDecimal("4000"));
TransactionNode e = new TransactionNode("TXN-E", new BigDecimal("5000"));
a.next = b; b.next = c; c.next = d; d.next = e; e.next = c; // cycle at C
TransactionNode start = CycleStartFinder.findCycleStart(a);
System.out.println("Cycle starts at: " + start.txnId);
}
}
Cycle starts at: TXN-C
How is this different from the hash-set approach?
The hash-set approach stores every visited node and returns the first node that is visited twice. It also finds the cycle start in O(n) time but uses O(n) space. Floyd's two-phase method achieves the same result in O(1) space.
| Feature | Floyd's Two-Phase | Hash-Set Approach |
|---|---|---|
| Time | O(n) | O(n) |
| Space | O(1) | O(n) |
| Finds start directly | After two phases | Immediately on repeat visit |
| Code complexity | Requires math understanding | Straightforward |
import java.util.HashSet;
import java.util.Set;
public static TransactionNode findCycleStartHashSet(TransactionNode head) {
Set<TransactionNode> visited = new HashSet<>();
TransactionNode current = head;
while (current != null) {
if (!visited.add(current)) {
return current; // first revisited node is cycle start
}
current = current.next;
}
return null;
}
What are the edge cases?
The main edge cases are: no cycle (return null), single node pointing to itself (cycle start is that node), and cycle starting at the head itself.
package com.bank.service;
import com.bank.model.TransactionNode;
import java.math.BigDecimal;
public class CycleStartEdgeCases {
public static void main(String[] args) {
// No cycle
TransactionNode n1 = new TransactionNode("TXN-1", new BigDecimal("1000"));
n1.next = new TransactionNode("TXN-2", new BigDecimal("2000"));
System.out.println("No cycle: " + CycleStartFinder.findCycleStart(n1));
// Self-loop
TransactionNode self = new TransactionNode("TXN-SELF", new BigDecimal("500"));
self.next = self;
System.out.println("Self-loop: " + CycleStartFinder.findCycleStart(self).txnId);
// Cycle at head
TransactionNode h = new TransactionNode("TXN-H", new BigDecimal("100"));
TransactionNode t = new TransactionNode("TXN-T", new BigDecimal("200"));
h.next = t; t.next = h;
System.out.println("Cycle at head: " + CycleStartFinder.findCycleStart(h).txnId);
}
}
No cycle: null
Self-loop: TXN-SELF
Cycle at head: TXN-H
How do you break the cycle once you find the start?
Once you know the cycle start node, you can walk from that node around the loop until you find the node whose next points back to the start, and set that next to null.
public static void breakCycle(TransactionNode head) {
TransactionNode cycleStart = CycleStartFinder.findCycleStart(head);
if (cycleStart == null) return;
TransactionNode runner = cycleStart;
while (runner.next != cycleStart) {
runner = runner.next;
}
runner.next = null; // break the cycle
System.out.println("Cycle broken at link from " + runner.txnId + " to " + cycleStart.txnId);
}
What about applications beyond linked lists?
The same two-phase technique applies to any sequence defined by repeatedly applying a function. The classic "find the duplicate number" problem uses array values as links: if nums[i] points to the next index, a duplicate creates a cycle, and Floyd's algorithm finds it in O(n) time and O(1) space.
package com.bank.service;
public class FindDuplicate {
public static int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[0];
// Phase 1: detect cycle
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// Phase 2: find entry
int entry = nums[0];
while (entry != slow) {
entry = nums[entry];
slow = nums[slow];
}
return entry;
}
public static void main(String[] args) {
int[] accountIds = {1, 3, 4, 2, 2}; // 2 is duplicate
System.out.println("Duplicate account ID: " + findDuplicate(accountIds));
}
}
Duplicate account ID: 2
What should a senior engineer know?
The elegance of phase two is that the distance equality a = nL - b falls directly from the two-to-one speed ratio. A senior engineer should be able to derive this from scratch rather than memorize it. The proof is short: slow travels a + b, fast travels 2(a + b), and the difference a + b must be a multiple of the loop length L.
In production at the National Bank of India, this algorithm is used in the chain repair tool. After detecting that an imported transaction chain has a loop, the tool needs the exact re-entry node so it can set the offending next pointer to null and restore a proper acyclic list.
package com.bank.service;
import com.bank.model.TransactionNode;
public class ChainRepairTool {
public static void repairChain(TransactionNode head) {
TransactionNode cycleStart = CycleStartFinder.findCycleStart(head);
if (cycleStart == null) {
System.out.println("Chain is clean, no cycle found.");
return;
}
TransactionNode runner = cycleStart;
while (runner.next != cycleStart) {
runner = runner.next;
}
System.out.println("Repairing: breaking link from " + runner.txnId
+ " back to " + cycleStart.txnId);
runner.next = null;
}
}
Visual Overview
Phase 1: Floyd's Detection
head ──> [A] ──> [B] ──> [C] ──> [D] ──> [E]
▲ │
└───────────────┘
slow and fast start at head
They meet somewhere inside the cycle (meeting point)
Phase 2: Find Cycle Start
entry = head slow = meeting point
│ │
▼ ▼
[A] ──> [B] ──> [C] [meeting] ──> ... ──> [C]
▲ │
└── both arrive here ───────────┘
Distance from head to C = Distance from meeting to C
(around the loop)
Key Takeaway
Linked List Cycle II finds the exact node where a cycle begins using two elegant phases. In phase one, Floyd's tortoise and hare detect the cycle by moving slow by one and fast by two until they meet inside the loop. In phase two, one pointer resets to the head while the other stays at the meeting point, and both advance one step at a time. They meet at the cycle's entry node.
The mathematics behind phase two is what makes this beautiful. If the distance from head to cycle start is a, and the slow pointer traveled a + b to the meeting point, then because fast traveled twice as far, 2(a + b) = a + b + nL, which simplifies to a = nL - b. That means the distance from the head to the entry equals the distance from the meeting point around to the entry. Two pointers advancing one step from those two positions will arrive at the same place.
The hash-set alternative finds the start by storing every visited node and returning the first repeat, but it costs O(n) space. Floyd's two-phase method accomplishes the same in O(1) space, which matters in memory-constrained environments like the import pipeline at National Bank of India.
In our banking system, the chain repair tool uses this algorithm after detecting a loop in imported transaction data. It finds the exact re-entry node, sets the offending next pointer to null, and restores a proper acyclic chain. The same two-phase technique also applies to the "find the duplicate number" problem, where array values are treated as links and a duplicate creates a cycle.
Remember one sentence: after the tortoise and hare meet, reset one to the head, walk both by one, and they meet at the cycle start because a = nL - b.
---