Start of LinkedList Cycle
Mahabharata — Tracing the Chakravyuha — Finding Where the Trap Begins
चक्रारम्भं यदि ज्ञातुं इच्छसे धीर पाण्डव। संगमस्थानात् मूलं गच्छ — आद्यं तत्र भविष्यति॥
*If you wish to know the beginning of the cycle, O wise Pandava — walk from the meeting point to the origin and you shall find it there.*
The Story
The Chakravyuha had been confirmed cyclic. Abhimanyu was trapped inside it. But Yudhishthira needed to know something more precise: at which exact node did the spiral begin? Which general commanded the gate through which our spy first entered the loop?
"Finding the cycle exists is not enough," Yudhishthira told Sahadeva. "I need to know the entry point — the first soldier Abhimanyu could not pass, the node where the spiral snaps shut."
Sahadeva sat quietly, his eyes distant with the knowledge of past and future. "After the two scouts met inside the cycle, we have information we have not yet used."
"What information?"
"The distance from the meeting point to the cycle's start is the same as the distance from the list's head to the cycle's start."
Yudhishthira stared. "How can that be?"
Sahadeva drew a diagram in the dust:
"Let F = length of the path before the cycle begins. Let C = total length of the cycle. Let K = the node within the cycle where slow and fast met."
"The slow pointer has traveled: F + K steps." "The fast pointer has traveled: F + K + some_full_loops × C steps. But also exactly 2 × (F + K) steps, since it moved at double speed."
"Setting equal: 2(F + K) = F + K + m×C for some integer m." "Simplify: F + K = m×C." "Therefore: F = m×C - K."
"This means: starting from the meeting point and walking F more steps brings you back to the cycle start (since m full loops is just going around, and -K means you end up F steps before the start from the other direction... actually it means the remaining distance from the meeting point to the cycle start is exactly F steps). And F steps from the head also reaches the cycle start."
"So," Sahadeva concluded, his voice calm as the eye of a storm, "after the two scouts meet, reset one scout to the HEAD of the list. Keep the other at the MEETING POINT. Now advance both exactly ONE step at a time. They will meet again at the cycle's start."
Yudhishthira looked skeptical. "Why would they both arrive at the same place?"
"Because one is walking F steps from the head, and the other is walking F steps from the meeting point (which is equivalent to F steps from the cycle start going around). They each walk exactly F steps and arrive at the same place — the cycle start."
A scout was sent back to the entrance of the battle formation (head). The meeting-point scout stayed in position. Both began moving one step at a time.
Twenty-three steps later, they both stood at the same soldier — the seventh layer guardian, the precise node where the Chakravyuha's loop began. This was the traitor among generals who had sealed the exit.
"Node 7," Sahadeva said. "That is the entry to the cycle. Any warrior who reaches that position is trapped in the loop forever unless they can defeat all six warriors in sequence — which requires knowing both the entry AND exit maneuver."
"Abhimanyu knew the entry," Yudhishthira said quietly. "Only his father Arjuna knew the exit. And Arjuna was not here."
The mathematical beauty of Sahadeva's method echoed through the tragedy: two pointers, one reset to the start, converge on the cycle's beginning with perfect precision — no guessing, no HashSets, no marking of nodes.
"This is how you find not just that a trap exists," Sahadeva said, "but precisely where it begins."
This is the Fast & Slow Pointer technique for finding the start of a linked list cycle.
The Scout Master's First Instinct
Use a HashSet to find the first node visited twice — that's the cycle start. O(n) space.
public ListNode detectCycleBruteForce(ListNode head) {
Set<ListNode> visited = new HashSet<>();
ListNode current = head;
while (current != null) {
if (visited.contains(current)) {
// First node seen twice = cycle start
return current;
}
visited.add(current);
current = current.next;
}
return null; // No cycle
}Sahadeva's Wisdom
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
// Phase 1: Detect if cycle exists and find meeting point
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// Cycle confirmed, meeting point found
// Phase 2: Find cycle start
fast = head; // Reset fast to head
// Now move both one step at a time
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // This is the cycle start
}
}
return null; // No cycle
}
// Test: 0 → 1 → 2 → 3 → 4 → 2 (cycle starts at node 2)
public static void main(String[] args) {
ListNode head = new ListNode(0);
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
head.next = n1; n1.next = n2; n2.next = n3;
n3.next = n4; n4.next = n2; // cycle back to n2
ListNode start = new Solution().detectCycle(head);
System.out.println("Cycle starts at node: " + start.val); // 2
}Step-by-Step Walkthrough
List: head → A → B → C → D → B (cycle starts at B)
F=2 (head→A→B), cycle length C=3 (B→C→D→B)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 1 — Find meeting point
Start: slow=head, fast=head
Round 1: slow=A, fast=B
Round 2: slow=B, fast=D (B.next.next=D)
Round 3: slow=C, fast=C (D.next.next=C)
Meeting at C!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 2 — Find cycle start
Reset fast = head
Now: slow=C (in cycle), fast=head
Step 1: slow=D, fast=A
Step 2: slow=B, fast=B ← MEET!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Cycle starts at B
Math: F=2 steps from head, both pointers traveled 2 steps
slow: C→D→B (2 steps in cycle)
fast: head→A→B (2 steps from head)Deep Insight
**The mathematical beauty:**
Let: F = steps from head to cycle start, C = cycle length, K = steps from cycle start to meeting point.
slow traveled: F + K fast traveled: F + K + n·C (for some integer n, because fast lapped the cycle) But fast = 2 × slow: 2(F + K) = F + K + n·C Therefore: F + K = n·C → F = n·C - K
This means: from the meeting point (K steps into the cycle), going F more steps forward in the cycle = n full cycles - K + K = n full cycles = back to cycle start.
So: one pointer from head + one pointer from meeting point, both moving at speed 1, both travel F steps to reach cycle start simultaneously.
**Edge cases:** - No cycle: Phase 1 terminates at null, return null - Cycle starts at head (F=0): They meet at head in Phase 2 immediately - Cycle of length 1 (self-loop): works correctly
**Why n=1 works in the simple case:** For most typical interview problems, the first overlap happens at n=1, meaning F = C - K. The math works for any n.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | HashSet stores all nodes until cycle start is found |
| Optimal | O(n) | O(1) | Two passes total, only two pointer variables |
Pattern Recognition
✅ Linked list with a cycle ✅ Need to find ENTRY POINT of cycle (not just detect) ✅ O(1) space constraint ✅ Two-phase algorithm required **LeetCode Trigger Phrases:** → "return the node where the cycle begins" → "find the entrance to the cycle" → "O(1) space" + "linked list cycle"
Bhagavad Gita 13.13
अनादिमत्परं ब्रह्म न सत्तन्नासदुच्यते। सर्वतः पाणिपादं तत् सर्वतोऽक्षिशिरोमुखम्॥
The supreme Brahman is without beginning, is neither being nor non-being. It has hands and feet everywhere, eyes and heads and mouths everywhere.
Connection: Just as the origin of existence is traced by following the patterns of consciousness back to their source, the algorithm traces the cycle back to its beginning. The two pointers converge not at a random point but at the precise origin — the first node of the cycle. Like finding the source of a river by following its tributaries backward, this technique finds where infinite repetition first began.