LinkedList Cycle
Mahabharata — The Chakravyuha — Abhimanyu Trapped in the Spiral
शीघ्रः मन्दश्च द्वावेव यदि एकस्मिन् पथि यान्ति। चक्रे सम्मिलितौ स्यातां चक्रमस्ति इति निश्चितम्॥
*If the swift and the slow both travel the same path, and they meet — it is certain a cycle exists.*
The Story
On the thirteenth day of Kurukshetra, the Kaurava generals deployed the Chakravyuha — the spiral battle formation, a living labyrinth that rotated like a wheel, trapping anyone who entered without knowing the exit. Six warriors guarded each layer of the spiral, and the paths between them looped back on themselves in an inescapable cycle.
Yudhishthira's scouts returned with grim news: "My Lord, our spy entered the formation three hours ago. He has not emerged. But we don't know if the spiral is truly cyclic — perhaps he is simply taking a long path through."
"How do we confirm the cycle without entering ourselves?" Yudhishthira asked.
Sahadeva, the youngest and wisest Pandava, the one blessed with knowledge of the future, spoke quietly: "Send two scouts. One cautious, one swift. The cautious scout moves one node at a time through the formation's paths. The swift scout moves two nodes at a time — double speed."
"If the formation has no cycle," Sahadeva continued, "the swift scout will simply reach the end first. He will return and tell us: no trap, just a long road."
"But if the formation IS cyclic?" Yudhishthira pressed.
"Then neither scout will ever reach an end. They will keep looping. But here is the critical insight, brother: the swift scout gains one node on the cautious scout every step. In a cycle of length L, after at most L steps, the swift scout has lapped the slow one and they will meet at the same node. Their meeting is proof of the cycle."
Yudhishthira frowned. "How can we be certain they will ALWAYS meet, and not always remain apart?"
Sahadeva drew in the dust:
"Imagine the cycle has length L. The slow scout moves 1 step, the fast moves 2. The gap between them decreases by 1 each round. If the gap is initially G, after G rounds the gap is 0 — they meet. Since the gap is always between 0 and L, they must meet within L steps after the slow scout enters the cycle."
"What if the cycle is very long? Could they orbit forever without meeting?"
"No. Each step the fast scout is exactly 1 node closer to the slow scout (modulo L). Like a faster runner on a circular track — they MUST meet the slower runner eventually."
Two scouts were dispatched. The cautious one (slow) stepped one node at a time through the Chakravyuha. The swift one (fast) leaped two nodes at a time. Within minutes, shouts rose from the formation: they had met at the same position, proving the cycle existed.
"Our spy is trapped," Yudhishthira concluded. "The Chakravyuha is indeed a closed loop."
Only Abhimanyu knew how to enter the Chakravyuha. Tragically, he had never learned how to exit. He charged in, brave and brilliant — the equivalent of a pointer entering a cycle with no null to terminate at. He went in circles, fighting each layer again and again, until surrounded from all sides.
Krishna, watching from a distance, whispered to Arjuna: "This is the peril of a cycle with no exit. The fast pointer and slow pointer can detect the trap — but detecting it does not free you from it. To find the exit, we need a different technique."
But that — finding where the cycle begins — was a problem for another day.
"Today, at least, we know the trap is real," Sahadeva said. "Two scouts, one fast, one slow. If they meet, the path loops. If the fast one reaches the end safely, the path is free."
This is the Fast & Slow Pointer technique for detecting a cycle in a linked list.
The Scout Master's First Instinct
Use a HashSet to remember every node visited. If we ever visit a node we've seen before, a cycle exists. O(n) time but O(n) space — storing all visited nodes.
public boolean hasCycleBruteForce(ListNode head) {
// Remember every node we've visited
Set<ListNode> visited = new HashSet<>();
ListNode current = head;
while (current != null) {
// Have we been here before?
if (visited.contains(current)) {
return true; // Cycle detected!
}
visited.add(current);
current = current.next;
}
// Reached null — no cycle
return false;
}Sahadeva's Wisdom
public boolean hasCycle(ListNode head) {
// Both scouts start at the entrance
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // Cautious scout: 1 step
fast = fast.next.next; // Swift scout: 2 steps
// They met — cycle confirmed!
if (slow == fast) return true;
}
// Fast scout reached the end — no cycle
return false;
}
// Test with a cyclic list: 1 → 2 → 3 → 4 → 2 (cycle back)
public static void main(String[] args) {
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = head.next; // cycle back to 2
System.out.println(new Solution().hasCycle(head)); // true
}Step-by-Step Walkthrough
List: 3 → 2 → 0 → -4 → 2 (cycle, tail connects to node at index 1) Nodes: [3] → [2] → [0] → [-4] → back to [2] ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Initial: slow=[3], fast=[3] ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Round 1: slow = slow.next → slow=[2] fast = fast.next.next → fast=[0] slow ≠ fast, continue ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Round 2: slow = slow.next → slow=[0] fast = fast.next.next → fast=[-4].next=[2] slow ≠ fast, continue ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Round 3: slow = slow.next → slow=[-4] fast = fast.next.next → fast=[0].next.next=[-4] slow=[-4] == fast=[-4] → ✅ CYCLE DETECTED! ✅ Return true
Deep Insight
**Why do they always meet in a cycle?**
Consider the moment the slow pointer enters the cycle. Let the fast pointer be k nodes ahead in the cycle (of length L). Each round, the distance between them (measured inside the cycle) decreases by 1. After k rounds, the distance is 0 — they meet. Since k < L, they meet within L rounds of the slow pointer entering the cycle.
**Total time: O(n).** The slow pointer travels at most n steps before entering the cycle (the non-cyclic prefix), then at most L more steps to meet the fast pointer. So at most 2n total steps.
**Edge cases:** - Empty list (head == null): `fast != null` fails immediately, return false - Single node with no self-loop: `fast.next == null`, return false - Single node with self-loop (head.next = head): Round 1: slow=head, fast=head, they're equal! Return true
**Why check `fast.next != null`?** Because `fast.next.next` would throw NullPointerException if `fast.next` is null.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | HashSet stores all n visited nodes |
| Optimal | O(n) | O(1) | Only two pointer variables, no storage of visited nodes |
Pattern Recognition
✅ Linked list traversal ✅ Cycle/loop detection required ✅ O(1) space constraint ✅ Cannot use visited set or modify nodes **LeetCode Trigger Phrases:** → "detect if a linked list has a cycle" → "determine if there is a cycle in the linked list" → "without using extra space" + linked list
Bhagavad Gita 2.28
अव्यक्तादीनि भूतानि व्यक्तमध्यानि भारत। अव्यक्तनिधनान्येव तत्र का परिदेवना॥
Beings are unmanifest in the beginning, manifest in the middle, and unmanifest again at the end. What is there to grieve about?
Connection: The linked list cycle is the algorithmic mirror of samsara — the endless cycle of birth and death with no manifest end. The fast and slow pointers, like souls on the path, travel through existence. If the path has an end (null), the fast pointer finds it first and liberation (return false) is clear. But if trapped in the cycle of repeated births, they inevitably meet — two souls at the same point of the wheel, confirming the cycle that binds them.