Middle of the LinkedList
Ramayana — Hanuman Bisects Lanka — Finding the Exact Center of the Island Fortress
यस्त्वरितं गच्छति द्विगुणं स मध्यं दर्शयति। शनैः शनैरेकः गच्छन् तत्र तिष्ठति निश्चयात्॥
*One who goes at double speed points to the middle. The one who goes slowly, step by step, stands there certainly.*
The Story
When Hanuman landed on the shores of Lanka after his legendary leap across the ocean, he faced a reconnaissance problem that would determine the success of Rama's entire campaign. Lanka was a vast island-fortress, its districts arranged in a linear chain of towers from the northern shore to the southern, each tower connected by a single passage to the next.
Hanuman needed to find the central tower — the midpoint of Lanka's defense chain. From the center, he could observe both halves simultaneously, send signals in either direction with equal speed, and plant the crucial intelligence that would guide Rama's army.
"Lanka has n districts in a chain," Vibhishana, Ravana's righteous brother who secretly aided Hanuman, whispered from the shadows. "I don't know n. The chain could be odd or even. But I can guide you."
"Can we not simply count to n, divide by two, and walk there?" Hanuman's scout Sampati suggested.
"That requires a full pass to count, then another half-pass to reach the middle," Vibhishana replied. "Two passes, 1.5n total steps. I have a way that requires only one pass."
"In one pass?"
"Watch." Vibhishana pointed north. "Send two scouts — one cautious, one swift. The cautious scout walks one district per time-step. The swift scout walks two districts per time-step. When the swift scout reaches the end of Lanka, the cautious scout will be exactly at the middle."
Hanuman saw the elegance immediately. "Because the swift scout covers twice the distance — when he has gone n steps, the cautious scout has gone n/2 steps!"
"Precisely. And this works whether n is odd or even."
"If n is odd — say 7 districts:" "Swift scout reaches district 7 (end) after 3.5 steps... but we step in integers, so after 3 steps he's at district 6, one step from end. After 4 steps he reaches district 7. But we stop when fast.next == null (can't move 2 more)."
"Actually," Vibhishana corrected, "the check is: advance fast if fast.next is not null AND fast.next.next is not null. So for 7 districts:"
"Round 1: slow=2, fast=3" "Round 2: slow=3, fast=5" "Round 3: slow=4, fast=7" "fast.next == null → stop. Slow is at district 4 — the middle of 7 (4th out of 7, with 3 before and 3 after)."
"And if n is even — say 6 districts:" "Round 1: slow=2, fast=3" "Round 2: slow=3, fast=5" "fast.next.next == null (would go past end) → stop. Slow is at district 3." "But the middle of 6 is between 3 and 4 — for even-length, we return the SECOND middle node (district 4)... wait, the convention matters."
Vibhishana smiled. "The LeetCode problem returns the second middle for even-length lists. With our termination condition `while (fast != null && fast.next != null)`, for n=6:" "Round 1: slow=2, fast=3" "Round 2: slow=3, fast=5" "Round 3: slow=4, fast=7... but n=6, so fast can reach district 5 (odd positions 1-6): wait let me redo with 0-indexed nodes."
Hanuman held up his hand. "I will test with actual districts."
1→2→3→4→5 (5 districts): Start: slow=1, fast=1 Round 1: slow=2, fast=3. Fast.next (4) and fast.next.next (5) both exist. Round 2: slow=3, fast=5. Fast.next (null) doesn't exist. STOP. Return slow=3 ✓ (middle of 5)
1→2→3→4→5→6 (6 districts): Start: slow=1, fast=1 Round 1: slow=2, fast=3. Both .next.next exist. Round 2: slow=3, fast=5. fast.next=6, fast.next.next=null. STOP. Return slow=4 ✓ (second middle of 6)
Hanuman dispatched two ghost-scouts into Lanka's district chain. When the fast scout could no longer advance two steps, the slow scout stood at the precise center. From there, Hanuman surveyed all of Lanka — the ashoka grove where Sita was held, the garrison towers, the approach paths.
"One pass, O(1) space, exact center," Vibhishana said. "No counting, no second traversal."
This single reconnaissance from Lanka's center gave Hanuman everything he needed to plan Rama's invasion. The mid-point was not just a number — it was the strategic heart of the problem.
This is the Fast & Slow Pointer technique for finding the middle of a linked list.
Sampati's First Instinct
Count all nodes (one full pass), then walk to n/2 (half pass). Two passes total, still O(n) but takes 1.5n steps and requires storing the count.
public ListNode middleNodeBruteForce(ListNode head) {
// Pass 1: Count all nodes
int count = 0;
ListNode current = head;
while (current != null) {
count++;
current = current.next;
}
// Pass 2: Walk to the middle (count/2 steps)
int middleIndex = count / 2;
current = head;
for (int i = 0; i < middleIndex; i++) {
current = current.next;
}
return current; // Middle node
}Vibhishana's Wisdom
public ListNode middleNode(ListNode head) {
ListNode slow = head; // Cautious scout: 1 step
ListNode fast = head; // Swift scout: 2 steps
// Stop when fast can't take 2 more steps
while (fast != null && fast.next != null) {
slow = slow.next; // 1 step forward
fast = fast.next.next; // 2 steps forward
}
// Slow is now at the middle
return slow;
}
// Test cases
public static void main(String[] args) {
// Odd length: 1→2→3→4→5 → middle = 3
ListNode head1 = buildList(new int[]{1, 2, 3, 4, 5});
System.out.println(middleNode(head1).val); // 3
// Even length: 1→2→3→4→5→6 → middle = 4 (second middle)
ListNode head2 = buildList(new int[]{1, 2, 3, 4, 5, 6});
System.out.println(middleNode(head2).val); // 4
}Step-by-Step Walkthrough
List: 1 → 2 → 3 → 4 → 5 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Initial: slow=[1], fast=[1] ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Round 1: slow=[1]→slow=[2] fast=[1]→fast=[3] (2 steps) fast.next=[4] ≠ null, fast.next.next=[5] ≠ null → continue ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Round 2: slow=[2]→slow=[3] fast=[3]→fast=[5] (2 steps) fast.next=null → STOP! ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ✅ Return slow=[3] Verify: [1,2,3,4,5] — node 3 is the middle with 2 nodes on each side ✓
Deep Insight
**Why does fast reaching null mean slow is at middle?**
Each round, slow moves +1 and fast moves +2. After k rounds: slow = head + k, fast = head + 2k. When fast = end (n-1), we have 2k = n-1, so k = (n-1)/2. Slow is at head + (n-1)/2 = the middle!
**Odd vs Even:** - Odd (n=5): After 2 rounds, slow=3, fast=5 (end). Middle = node 3 (the exact center). - Even (n=6): After 3 rounds, slow=4, fast=7 (would go past end). We stop at fast.next.next=null. Middle = node 4 (the second of two middle nodes).
**Edge cases:** - Single node: fast.next=null immediately, return head - Two nodes: Round 1 — slow=node2, fast reaches end (fast.next=null). Return node2 (second middle) - Head is null: fast starts as null, while condition is false immediately — but problem guarantees non-empty list
**Use case beyond this problem:** Finding the middle is a subroutine in: - Merge Sort on linked lists - Palindrome linked list check (fs-6) - Reorder linked list (fs-7)
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Two passes: count (n steps) + walk to middle (n/2 steps) = 1.5n total |
| Optimal | O(n) | O(1) | Single pass of at most n/2 rounds |
Pattern Recognition
✅ Linked list of unknown length ✅ Find middle node in one pass ✅ O(1) space required ✅ Fast pointer at 2x speed of slow pointer **LeetCode Trigger Phrases:** → "return the middle node of the linked list" → "if two middle nodes... return the second" → "find the middle in one pass"
Bhagavad Gita 15.15
सर्वस्य चाहं हृदि सन्निविष्टो मत्तः स्मृतिर्ज्ञानमपोहनं च। वेदैश्च सर्वैरहमेव वेद्यो वेदान्तकृद्वेदविदेव चाहम्॥
I am seated in the hearts of all beings. From Me come memory, knowledge, and reasoning. By all the Vedas, I am alone to be known; I am the author of Vedanta and the knower of the Vedas.
Connection: The middle node is the heart of the linked list — it is 'seated' at the center of all nodes, with equal reach to both ends. Just as the divine resides in the center of all beings, the middle node is the strategic heart from which both halves can be reached with equal steps. The fast-slow technique, like divine omniscience, finds this center in a single sweep without the need to count all nodes first.