Palindrome LinkedList
Ramayana — Valmiki's Palindromic Verse — The Shloka That Reads the Same Forwards and Backwards
तपःस्वाध्यायनिरतं तपस्वी वाग्विदां वरम्। नारदं परिपप्रच्छ वाल्मीकिर्मुनिपुङ्गवम्॥
*Valmiki, best among sages, questioned Narada, who was always engaged in austerity, self-study, and speech — the very first verse whose mirror tells the tale of Rama.*
The Story
The sage Valmiki sat by the banks of the Tamasa river, deep in meditation, when a hunter's arrow struck a krauncha bird in mid-flight. The bird's mate cried out in grief, and from that primal sorrow sprang the first shloka in human history — and it was a palindrome.
The grief-born syllables echoed: *maa nishada pratistham tva-magamah shashvatih samah / yat krauncha mithunaat ekam avadhih kaama mohitam* — some scholars noticed that certain sacred verses of the Ramayana, when read in Sanskrit syllable-units, carry the same melody whether chanted forward or backward. The universe had encoded its own symmetry in the first poem.
Valmiki's apprentice Bharadvaja was tasked with verifying which verses from the ten thousand shlokas of the Ramayana had this palindromic property. Each verse was stored as a linked list of syllable-nodes.
"Master, how can I check if a verse-list is palindromic without copying it?" Bharadvaja asked. "The obvious approach is to convert the entire list to an array and check indices from both ends."
"That uses O(n) space — space proportional to the verse length," Valmiki replied. "For ten thousand verses, this is wasteful. There is a way to check in O(1) space."
"How?"
Valmiki took a lotus leaf and scratched four steps:
**Step 1:** Find the middle of the verse-list using fast & slow pointers. **Step 2:** Reverse the second half of the list in-place. **Step 3:** Compare the first half (forward) with the reversed second half (forward). **Step 4:** Restore the second half (optional, for politeness) and return the result.
"If every syllable in the first half matches its mirror in the reversed second half, the verse is a palindrome," Valmiki said.
Bharadwaja traced through an example: `1 → 2 → 3 → 2 → 1`
**Step 1:** Find middle. slow=1, fast=1 Round 1: slow=2, fast=3 Round 2: slow=3, fast=5 (end) Middle = node(3)
**Step 2:** Reverse second half (from middle.next = node(2)). Original second half: 2 → 1 → null Reversed: null ← 2 ← 1, i.e., 1 → 2 → null
**Step 3:** Compare. First half: node(1) → node(2) → [stop at middle] Reversed second: node(1) → node(2) 1==1 ✓, 2==2 ✓ All match! Palindrome!
"But what about even-length verses?" Bharadwaja asked. "Like `1 → 2 → 2 → 1`?"
**Step 1:** Middle = node(2) at index 1 (second node). Actually for even length [1,2,2,1], fast pointer: slow=1, fast=1 Round 1: slow=2, fast=3 Round 2: slow=2(index2), fast=null.next... wait: fast=3.next.next=null → stop when fast.next=null. Hmm: fast.next = node(1), fast.next.next = null → stop! slow = node(2) (second node).
**Step 2:** Reverse from slow.next = node(2)(third node). Second half: 2 → 1. Reversed: 1 → 2.
**Step 3:** Compare first half [1,2] with reversed second [1,2]: match!
"Brilliant," Bharadwaja breathed. "Three operations, no extra array."
"The Ramayana itself," Valmiki said softly, watching the river, "is a palindrome of the human spirit. The exile begins with sorrow and ends with return. The first words of grief and the last words of reunion — if you listen carefully, they carry the same emotional weight, mirroring each other across time."
Bharadwaja checked verse after verse through the night. Many were palindromic — the divine love of Ram and Sita encoded in a symmetry that human language had unconsciously discovered thousands of years before mathematicians would name it.
This is the Fast & Slow Pointer technique for checking a palindrome linked list.
Bharadwaja's First Instinct
Copy all values to an array, then use two pointers from both ends. O(n) space for the array.
public boolean isPalindromeBruteForce(ListNode head) {
// Copy all values to a list
List<Integer> values = new ArrayList<>();
ListNode current = head;
while (current != null) {
values.add(current.val);
current = current.next;
}
// Check palindrome with two pointers
int left = 0, right = values.size() - 1;
while (left < right) {
if (!values.get(left).equals(values.get(right))) {
return false;
}
left++;
right--;
}
return true;
}Valmiki's Wisdom
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// Step 1: Find the middle
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow is now at the middle (second middle for even length)
// Step 2: Reverse the second half
ListNode secondHalf = reverseList(slow);
ListNode secondHalfCopy = secondHalf; // save for restoration
// Step 3: Compare first half with reversed second half
ListNode firstHalf = head;
boolean palindrome = true;
while (secondHalf != null) {
if (firstHalf.val != secondHalf.val) {
palindrome = false;
break;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
// Optional Step 4: Restore the list (good practice)
reverseList(secondHalfCopy);
return palindrome;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
// Test cases
public static void main(String[] args) {
// 1→2→3→2→1 → true
// 1→2→2→1 → true
// 1→2→3 → false
}Step-by-Step Walkthrough
List: 1 → 2 → 3 → 2 → 1 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ STEP 1 — Find middle Initial: slow=[1], fast=[1] Round 1: slow=[2], fast=[3] Round 2: slow=[3], fast=[1](last) → fast.next=null → STOP Middle = [3] ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ STEP 2 — Reverse second half (starting from [3]) Before: [3] → [2] → [1] → null After: [1] → [2] → [3] → null secondHalf head = [1] ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ STEP 3 — Compare firstHalf: [1] → [2] → [3] → ... secondHalf: [1] → [2] → [3] → null Compare [1] == [1] ✓ Compare [2] == [2] ✓ secondHalf exhausted (null) → DONE ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ✅ Return true — palindrome confirmed
Deep Insight
**Why does reversing in-place work for O(1) space?**
We modify the list's own `.next` pointers during reversal — no new nodes are created. Three pointers (`prev`, `current`, `next`) are all we need. After comparison, we reverse again to restore the original structure.
**Odd vs Even handling:** - Odd (n=5): Middle = 3rd node. Second half has 2 nodes; first half has 2 meaningful nodes to compare (node 1, 2) with reversed second (node 4, 5 → reversed to 5,4 direction... no, value comparison: [1,2] vs [1,2] for a palindrome). - Even (n=4, [1,2,2,1]): Middle = 2nd node (for even, we stop at 2nd). Second half has 2 nodes [2,1], reversed = [1,2]. First half [1,2]. Compare: 1==1, 2==2 ✓.
**Why stop secondHalf iteration, not firstHalf?** Second half is always ≤ first half in length (for odd n, first half has the middle + left). We iterate while secondHalf != null, which handles both odd and even correctly.
**Restoring the list:** Interviews often expect the original structure to be preserved. Calling reverseList again on the second half restores it.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | ArrayList to store all n node values |
| Optimal | O(n) | O(1) | Three in-place operations, only pointer variables |
Pattern Recognition
✅ Linked list palindrome check ✅ O(1) space required ✅ Multi-step: find middle + reverse + compare ✅ In-place modification with optional restoration **LeetCode Trigger Phrases:** → "determine if a linked list is a palindrome" → "O(1) space" + palindrome + linked list → "reverse second half" (hint in problem comments)
Bhagavad Gita 13.13
अनादिमत्परं ब्रह्म न सत्तन्नासदुच्यते। सर्वतः पाणिपादं तत् सर्वतोऽक्षिशिरोमुखम्॥
The supreme exists beyond beginning and end — it is neither being nor non-being, yet it has hands and feet, eyes and heads and mouths in every direction.
Connection: A palindrome is a structure that is the same whether you approach it from the beginning or the end — like the eternal self that exists beyond the asymmetry of birth and death. The algorithm reads the list forward from one end and the reversed list forward from what was the other end — and they tell the same story. This is the computational equivalent of the Gita's teaching that the supreme reality is symmetric, unbounded by the direction of time.