77. Palindrome Linked List
🔗 LeetCode Problem: 234. Palindrome Linked List
📊 Difficulty: Easy (but uses Medium techniques!)
🏷️ Topics: Linked List, Two Pointers, Stack, Recursion
Problem Statement
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Example 1:
Input: head = [1,2,2,1]
Output: true
Visual:
1 -> 2 -> 2 -> 1
↑ ↑
Same from both ends!
Example 2:
Input: head = [1,2]
Output: false
Visual:
1 -> 2
↑ ↑
Different!
Constraints:
- The number of nodes in the list is in the range [1, 10^5].
- 0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
🎨 Visual Understanding
The Problem Visualized
Example 1: Palindrome
List: 1 -> 2 -> 3 -> 2 -> 1 -> null
↑ ↑ ↑
Same Middle Same
Read forward: 1, 2, 3, 2, 1
Read backward: 1, 2, 3, 2, 1
Same! → Palindrome ✓
Example 2: Not Palindrome
List: 1 -> 2 -> 3 -> 4 -> null
↑ ↑
1 4
Read forward: 1, 2, 3, 4
Read backward: 4, 3, 2, 1
Different! → Not palindrome ✗
What is a Palindrome?
Same forwards and backwards!
Examples:
"racecar" → palindrome ✓
"hello" → not palindrome ✗
For linked list:
[1,2,3,2,1] → palindrome ✓
[1,2,3,4,5] → not palindrome ✗
🚨 CRITICAL INSIGHT - Two-Part Strategy!
The Key Pattern!
The challenge: Linked lists are one-directional!
We can only go forward, not backward!
To check palindrome, we need to compare:
First half vs Second half (reversed)
Solution: Split and compare!
1. Find middle (Fast & Slow Pointers)
2. Reverse second half
3. Compare first half with reversed second half
4. (Optional) Restore list
This is similar to Problem #76 (Reorder List)!
But instead of merging, we COMPARE! ✓
The Strategy Visualized
Original: 1 -> 2 -> 3 -> 2 -> 1
STEP 1: Find Middle
First half: 1 -> 2 -> 3
Second half: 2 -> 1
STEP 2: Reverse Second Half
First half: 1 -> 2 -> 3
Second half: 1 -> 2 (reversed!)
STEP 3: Compare
1 == 1? Yes ✓
2 == 2? Yes ✓
3 (middle, can ignore for odd length)
All match! Palindrome! ✓
Another Example (Not Palindrome):
Original: 1 -> 2 -> 3 -> 4
STEP 1: Split at middle
First: 1 -> 2
Second: 3 -> 4
STEP 2: Reverse second
First: 1 -> 2
Second: 4 -> 3 (reversed!)
STEP 3: Compare
1 == 4? No! ✗
Not a palindrome!
Why This Works
Palindrome property:
Mirror around the center!
1 -> 2 -> 3 -> 2 -> 1
↑
Center
Left of center: 1, 2
Right of center: 2, 1
If we reverse right side: 1, 2
Now compare: [1,2] == [1,2] ✓
Key insight:
By reversing the second half,
we can compare directly with first half!
If all elements match → palindrome!
If any mismatch → not palindrome!
🎯 Approach 1: Copy to Array (Simple)
The Most Natural Thinking 💭
Core Logic:
Copy all values to an array
Use two pointers from both ends
Compare values
Implementation
/**
* Copy to array and use two pointers
* Time: O(n), Space: O(n)
*/
public boolean isPalindrome(ListNode head) {
// Copy to array
List<Integer> values = new ArrayList<>();
ListNode current = head;
while (current != null) {
values.add(current.val);
current = current.next;
}
// Two pointers from both ends
int left = 0;
int right = values.size() - 1;
while (left < right) {
if (!values.get(left).equals(values.get(right))) {
return false;
}
left++;
right--;
}
return true;
}
⏰ Time: O(n) - Two passes
💾 Space: O(n) - Array to store values
✓ Simple, but uses extra space!
🎯 Approach 2: Reverse Second Half (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Three steps, all in-place:
1. Find middle (fast & slow)
2. Reverse second half
3. Compare first half with reversed second half
4. (Optional) Restore original list
No extra space needed! ✓
The Strategy:
Three-Step Algorithm:
Step 1: Find Middle
Use fast & slow pointers
Split list into two halves
Step 2: Reverse Second Half
In-place reversal
Step 3: Compare
Walk through both halves
Compare values
If all match → palindrome
If any mismatch → not palindrome
Time: O(n), Space: O(1) ✓
Implementation
/**
* Reverse Second Half and Compare
* Time: O(n), Space: O(1)
*/
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true; // Empty or single node is palindrome
}
// STEP 1: Find middle of the list
ListNode slow = head;
ListNode fast = head;
// Find middle using fast & slow pointers
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow is now at middle (or second middle for even)
// STEP 2: Reverse the second half
ListNode secondHalf = reverseList(slow);
ListNode firstHalf = head;
// STEP 3: Compare both halves
ListNode p1 = firstHalf;
ListNode p2 = secondHalf;
boolean isPalin = true;
while (p2 != null) { // Second half is shorter or equal
if (p1.val != p2.val) {
isPalin = false;
break;
}
p1 = p1.next;
p2 = p2.next;
}
// STEP 4 (Optional): Restore the list
// reverseList(secondHalf); // Uncomment if need to restore
return isPalin;
}
/**
* Helper: Reverse a linked list
*/
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next; // Save next
current.next = prev; // Reverse pointer
prev = current; // Move prev forward
current = next; // Move current forward
}
return prev; // New head
}
⏰ Time: O(n) - Three O(n) passes
💾 Space: O(1) - Only pointers
🔍 Dry Run
Example 1: [1,2,2,1] - Palindrome
Goal: Check if palindrome
Original: 1 -> 2 -> 2 -> 1 -> null
STEP 1: Find Middle
Initial:
slow = 1, fast = 1
Iteration 1:
slow = 2, fast = 2
Iteration 2:
slow = 2 (second one), fast = null
Loop ends
slow is at second 2 (index 2)
Split conceptually:
First half: 1 -> 2 (nodes 0, 1)
Second half: 2 -> 1 (nodes 2, 3, starting from slow)
STEP 2: Reverse Second Half
Call reverseList(2 -> 1):
Initial: prev = null, current = 2
Iteration 1:
next = 1
2.next = null
prev = 2, current = 1
Iteration 2:
next = null
1.next = 2
prev = 1, current = null
Return prev = 1
Result:
First half: 1 -> 2 -> ... (still connected)
Second half: 1 -> 2 -> null (reversed!)
STEP 3: Compare
p1 = 1 (first half start)
p2 = 1 (second half start)
Comparison 1:
p1.val (1) == p2.val (1)? Yes ✓
p1 = 2, p2 = 2
Comparison 2:
p1.val (2) == p2.val (2)? Yes ✓
p1 = 2 (second), p2 = null
p2 is null, loop ends
All matched! Return true ✓
Example 2: [1,2,3,4,5] - Not Palindrome
Goal: Check if palindrome
Original: 1 -> 2 -> 3 -> 4 -> 5 -> null
STEP 1: Find Middle
Fast & slow:
Initial: slow = 1, fast = 1
Step 1: slow = 2, fast = 3
Step 2: slow = 3, fast = 5
Step 3: slow = 4, fast = null
slow is at 4 (index 3)
Split:
First: 1 -> 2 -> 3 -> 4
Second: 4 -> 5 (starting from slow)
Wait, that's not quite right. Let me recalculate:
After fast/slow:
slow = 3 (middle for odd length)
Actually for odd length (5 nodes):
Iteration 1: slow = 2, fast = 3
Iteration 2: slow = 3, fast = 5
Iteration 3: slow = 4, fast = null (5.next = null)
slow = 4
STEP 2: Reverse from slow (4 -> 5)
Reverse 4 -> 5:
Result: 5 -> 4 -> null
Now:
First: 1 -> 2 -> 3 -> 4 (still connected through original links)
Second: 5 -> 4 -> null (reversed)
STEP 3: Compare
p1 = 1, p2 = 5
Comparison 1:
p1.val (1) == p2.val (5)? No! ✗
Return false immediately!
Example 3: [1,2,3,2,1] - Palindrome (Odd Length)
Original: 1 -> 2 -> 3 -> 2 -> 1 -> null
STEP 1: Find Middle
Fast & slow:
Initial: slow = 1, fast = 1
Step 1: slow = 2, fast = 3
Step 2: slow = 3, fast = 1 (wrapped)
Step 3: slow = 2 (second), fast = null
slow = 3 (middle element)
STEP 2: Reverse Second Half (from 3)
Reverse 3 -> 2 -> 1:
Result: 1 -> 2 -> 3 -> null (reversed!)
Now:
First: 1 -> 2 -> ...
Second: 1 -> 2 -> 3 -> null
STEP 3: Compare
p1 = 1, p2 = 1
1 == 1? Yes ✓
p1 = 2, p2 = 2
2 == 2? Yes ✓
p1 = 3, p2 = 3
3 == 3? Yes ✓
p1 = 2, p2 = null
Loop ends
All matched! Return true ✓
Note: For odd length, the middle element (3) appears
in both halves, so it compares with itself. This is fine!
🎯 Why This Works - Deep Dive
The Palindrome Property:
═══════════════════════════════════════════════════════════════
Palindrome: Mirror image around center!
For even length [1,2,2,1]:
First half: 1, 2
Second half: 2, 1
Reverse second: 1, 2
Compare: [1,2] == [1,2] ✓
For odd length [1,2,3,2,1]:
First half: 1, 2, 3
Second half: 2, 1
Reverse second: 1, 2
Compare: [1,2] == [1,2] ✓
Middle element (3) can be in either half,
doesn't affect palindrome property!
The Middle Element (Odd Length):
═══════════════════════════════════════════════════════════════
For odd length list:
The middle element always matches itself!
So we can include it in either half.
Example: [1,2,3,2,1]
Middle: 3
Option 1: First includes middle
First: [1,2,3]
Second: [2,1] -> Reversed: [1,2]
Compare first 2 elements: [1,2] == [1,2] ✓
Option 2: Second includes middle
First: [1,2]
Second: [3,2,1] -> Reversed: [1,2,3]
Compare: [1,2] == [1,2] (ignore extra 3) ✓
Either way works! We just compare shorter length.
Why Compare Until Second Half Ends:
═══════════════════════════════════════════════════════════════
while (p2 != null) {
compare p1 and p2
}
For odd length:
First half is one longer (includes middle)
Second half shorter
We only compare up to second half length!
The extra middle element doesn't affect result ✓
For even length:
Both halves equal length
Compare all elements ✓
Time Complexity:
═══════════════════════════════════════════════════════════════
Step 1: Find Middle
Fast & slow traverse entire list
Time: O(n)
Step 2: Reverse Second Half
Reverse n/2 nodes
Time: O(n/2) = O(n)
Step 3: Compare
Compare n/2 pairs
Time: O(n/2) = O(n)
Total: O(n) + O(n) + O(n) = O(n) ✓
Space: O(1) - Only pointers, no extra data structures
Why Reverse Is Necessary:
═══════════════════════════════════════════════════════════════
Problem: Linked list is one-directional!
Can't traverse backwards!
Solution: Reverse second half!
Now both halves go in "same" direction for comparison
Without reversal:
First: 1 -> 2 -> 3
Second: 4 -> 5 -> null
How to compare 3 with 4?
Can't go backwards from 5 to 4!
With reversal:
First: 1 -> 2 -> 3
Second: 5 -> 4 -> null (reversed!)
Now compare: 1 with 5, 2 with 4
Both going "forward" in their halves! ✓
🎯 Restoring the Original List (Optional)
/**
* Complete solution with list restoration
*/
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// Step 1: Find middle
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse second half
ListNode secondHalf = reverseList(slow);
ListNode firstHalf = head;
// Keep reference to second half start for restoration
ListNode secondHalfCopy = secondHalf;
// Step 3: Compare
boolean isPalin = true;
while (secondHalf != null) {
if (firstHalf.val != secondHalf.val) {
isPalin = false;
break; // Can break early but still need to restore!
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
// Step 4: Restore original list
reverseList(secondHalfCopy);
return isPalin;
}
Why restore? - Good practice to leave data structures unchanged - Some interviewers expect this - Shows attention to detail
⚠️ Common Mistakes to Avoid
Mistake 1: Wrong middle finding
// ❌ WRONG - Fast starts ahead
ListNode slow = head;
ListNode fast = head.next;
// Results in wrong middle!
// ✓ CORRECT - Both start at head
ListNode slow = head;
ListNode fast = head;
Mistake 2: Comparing wrong lengths
// ❌ WRONG - Might compare beyond second half
while (p1 != null && p2 != null) {
// Both could end at different times!
}
// ✓ CORRECT - Stop when second half ends
while (p2 != null) {
// Second half is shorter or equal
}
Mistake 3: Not handling odd length correctly
// ❌ WRONG - Tries to match middle with itself
// and gets confused
if (length % 2 == 1) {
// Special handling...
}
// ✓ CORRECT - Algorithm handles both automatically
// Just compare until second half ends!
Mistake 4: Forgetting edge cases
// ❌ WRONG - No null check
public boolean isPalindrome(ListNode head) {
ListNode slow = head; // What if head is null?
}
// ✓ CORRECT - Handle edge cases
if (head == null || head.next == null) {
return true;
}
Mistake 5: Modifying during comparison
// ❌ WRONG - Loses references
while (p2 != null) {
p1 = p1.next;
p2 = p2.next;
if (p1.val != p2.val) { // p1/p2 already moved!
return false;
}
}
// ✓ CORRECT - Check before moving
while (p2 != null) {
if (p1.val != p2.val) {
return false;
}
p1 = p1.next;
p2 = p2.next;
}
🎯 Pattern Recognition
Problem Type: Check Palindrome in Linked List
Core Pattern: Find Middle + Reverse + Compare
When to Apply:
✓ Check palindrome property
✓ Need O(1) space
✓ Linked list structure
✓ Compare elements symmetrically
✓ Can modify list (or restore after)
Recognition Keywords:
- "Palindrome"
- "Same forwards and backwards"
- "Mirror property"
- "Constant space" or "O(1) space"
- Linked list
Similar Problems:
- Reverse Linked List (LC 206) - Used in Step 2
- Middle of Linked List (LC 876) - Used in Step 1
- Reorder List (LC 143) - Similar technique
- Valid Palindrome (LC 125) - String version
Key Components:
┌────────────────────────────────────────────┐
│ Step 1: Find middle (fast & slow) │
│ Step 2: Reverse second half │
│ Step 3: Compare both halves │
│ Step 4: (Optional) Restore list │
│ Time: O(n), Space: O(1) │
└────────────────────────────────────────────┘
Combines multiple classic techniques!
🧠 Interview Strategy
Step 1: "Three-step approach: find middle, reverse, compare"
Step 2: "Use fast & slow to find middle"
Step 3: "Reverse second half in-place"
Step 4: "Compare first and reversed second"
Step 5: "All in-place, O(n) time, O(1) space"
Key Points to Mention:
- Three-step algorithm
- Find middle using fast & slow pointers
- Reverse second half to enable comparison
- Compare element by element
- Stop when second half ends (handles odd/even)
- Optional: restore list after comparison
- Time: O(n), Space: O(1)
- Alternative: Array O(n) space
Why This Approach?
"I'll use a three-step approach. First, I find the middle
using fast and slow pointers. This splits the list into two
halves. Second, I reverse the second half in-place. This is
crucial because linked lists are one-directional - reversing
lets me compare both halves going 'forward'. Third, I walk
through both halves comparing values. If all match, it's a
palindrome. For odd length, the middle element ends up in one
half but that's fine - we just compare until the shorter half
ends. This gives O(n) time with O(1) space."
Why Reverse Second Half?
"Since linked lists only go forward, I can't traverse backward
to compare. By reversing the second half, I transform the
comparison into two forward traversals that I can do
simultaneously. This avoids needing a stack or array."
Edge Cases to Mention:
✓ Empty list (palindrome)
✓ Single node (palindrome)
✓ Two nodes (check if equal)
✓ Odd length (middle in one half)
✓ Even length (equal halves)
📝 Quick Revision Notes
🎯 Core Concept:
Palindrome Linked List: Use 3-step algorithm! Step 1: Find middle (fast & slow). Step 2: Reverse second half. Step 3: Compare first vs reversed second. Stop when second ends (handles odd/even). All in-place! O(n) time, O(1) space!
⚡ Quick Implementation:
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Test {
public boolean isPalindrome(ListNode head) {
// Empty or single nodes.
if(head == null || head.next == null) {
return true;
}
// Approach: 4 step process.
// Examples: [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5, 6]
// in case of [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5, 6], slow becomes 3 and 4.
// odd length: [1,2,3,4,5] => [1,2,3] and [4,5] => [1,2,3] and [5,4] => [1,5,2,4,3]
// even length: [1,2,3,4,5,6] => [1,2,3,4] and [5,6] => [1,2,3,4] and [6,5] => [1,6,2,5,3,4]
// Step 1: Get middle node.
ListNode middleNode = getMiddleNode(head);
// Below is not required now.
// // Step 2: Cut into 2 halves.
// ListNode firstHalf = head;
// ListNode secondHalf = middleNode.next;
// middleNode.next = null; // actual cut
// Step 3: reverse the 2nd half.
ListNode secondHalf = reverse(middleNode);
ListNode firstHalf = head;
// Step 4: Merge both lists.
return compare(firstHalf, secondHalf);
}
private boolean compare(ListNode firstHalf, ListNode secondHalf) {
while (firstHalf != null && secondHalf != null) {
if(firstHalf.val != secondHalf.val) {
return false;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
private ListNode reverse(ListNode head) {
// 1 -> 2 -> 3 ===> null <- 1 <- 2 <- 3
ListNode curr = head;
ListNode prev = null;
while (curr != null) {
// Save the next node before updating links
ListNode next = curr.next;
// Point curr next to prev (reverse the link)
curr.next = prev;
// Update prev and curr pointers
prev = curr;
curr = next;
}
return prev; // because curr will be null and we break from loop.
}
private ListNode getMiddleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// in case of [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5, 6], slow becomes 3 and 4.
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " -> ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Test t = new Test();
ListNode head1 = new ListNode(1); // 1, 2, 3, 2, 1
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(2);
head1.next.next.next.next = new ListNode(1);
System.out.println(t.isPalindrome(head1)); // true
System.out.println(t.isPalindrome(null)); // empty list
System.out.println(t.isPalindrome(new ListNode(1))); // single element // true
ListNode head2 = new ListNode(1); // 2 elements
head2.next = new ListNode(1);
System.out.println(t.isPalindrome(head2)); // true
ListNode head3 = new ListNode(1); // 3 elements
head3.next = new ListNode(2);
head3.next.next = new ListNode(1);
System.out.println(t.isPalindrome(head3)); // true
ListNode head4 = new ListNode(1); // 2 elements
head4.next = new ListNode(2);
System.out.println(t.isPalindrome(head4)); // false
ListNode head5 = new ListNode(1); // 3 elements
head5.next = new ListNode(2);
head5.next.next = new ListNode(2);
System.out.println(t.isPalindrome(head5)); // false
}
}
🔑 Key Insights:
- Pattern: Find Middle + Reverse + Compare
- Step 1: Fast & slow to find middle
- Step 2: Reverse second half (critical!)
- Step 3: Compare while (second != null)
- Why Reverse: List is one-directional, need to compare forward
- Odd Length: Middle in one half, ignore during comparison
- Even Length: Both halves equal, compare all
- Stop Condition: When second half ends
- Time: O(n), Space: O(1)
🎪 Memory Aid:
"Find middle, flip second, compare forward!"
Think: "Split, Reverse, Match!" 🔄
💡 The Key Insight:
Palindrome: Mirror around center!
[1, 2, 3, 2, 1]
↑ ↑
Mirror middle!
To check:
First: [1,2,3]
Second: [2,1] → Reverse: [1,2]
Compare: [1,2] == [1,2] ✓
⚠️ Critical Details:
1. Step 1: Find middle (fast & slow)
2. slow ends at middle (or second middle for even)
3. Step 2: Reverse from slow
4. Standard reverse algorithm
5. Step 3: Compare while (second != null)
6. Check: first.val == second.val
7. Move both forward
8. Return true if all match
9. Odd length: middle element handled automatically
🔥 Why Each Step:
Step 1 (Find Middle):
Split into two halves
Makes reverse and compare manageable
Step 2 (Reverse Second):
Critical! Can't traverse backwards
Reversing makes both "forward" for comparison
Step 3 (Compare):
Walk both halves simultaneously
Compare element by element
Stop when shorter half ends
💡 Handling Odd vs Even:
Even [1,2,2,1]:
First: [1,2]
Second: [2,1] → Rev: [1,2]
Compare 2 elements ✓
Odd [1,2,3,2,1]:
First: [1,2,3]
Second: [2,1] → Rev: [1,2]
Compare 2 elements (ignore middle 3) ✓
Algorithm handles both automatically!
Just compare until second ends!
🧪 Edge Cases
Case 1: Empty list
Input: head = null
Output: true
(Empty is palindrome)
Case 2: Single node
Input: head = [1]
Output: true
(Single element is palindrome)
Case 3: Two nodes, same
Input: head = [1,1]
Output: true
Case 4: Two nodes, different
Input: head = [1,2]
Output: false
Case 5: Odd length palindrome
Input: head = [1,2,3,2,1]
Output: true
Case 6: Even length palindrome
Input: head = [1,2,2,1]
Output: true
Case 7: Not palindrome
Input: head = [1,2,3,4,5]
Output: false
All handled correctly! ✓
Related Patterns
- Reverse Linked List (LC 206) - Used in Step 2
- Middle of Linked List (LC 876) - Used in Step 1
- Reorder List (LC 143) - Similar three-step technique
- Valid Palindrome (LC 125) - String version
Happy practicing! 🎯
Note: This is another great problem that combines multiple techniques! It's marked "Easy" but uses Medium-level patterns. Master this and you'll have strong linked list fundamentals! The key is understanding why we reverse - it transforms a "backwards comparison" into a "forward comparison"! 🔄✨