🧩 Problem Overview
Given the head of a singly linked list, determine whether it is a palindrome.
A palindrome means the sequence reads the same forward and backward.
Example:
- Input: [1,2,2,1] → Output: true
- Input: [1,2] → Output: false
🎯 Why This Problem Matters
This problem tests:
- Linked list traversal
- Two-pointer technique (slow & fast)
- In-place reversal
It’s a must-know pattern for interviews.
🧠 Intuition
A simple approach is to copy elements into an array and check for palindrome.
But that uses extra space O(n).
Optimal Idea:
We can solve this in O(1) space by:
- Finding the middle of the linked list
- Reversing the second half
- Comparing both halves
🎥 Dry Run (Step-by-Step Explanation)
👉 Watch the complete dry run and pointer movement below:
This video explains how slow and fast pointers work and how the comparison is performed.
⚙️ Approach
Step 1: Handle Edge Cases
- If list has one node → return true
Step 2: Find Middle
- Use slow and fast pointers
- Fast moves 2 steps, slow moves 1
Step 3: Reverse Second Half
- Reverse the list starting from the middle
Step 4: Compare Both Halves
- Compare values from:
- start of list
- start of reversed half
💻 Java Solution
class Solution {
public ListNode reverse(ListNode head) {
ListNode curr = head;
ListNode prev = null;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
public boolean isPalindrome(ListNode head) {
if (head == null) return false;
if (head.next == null) return true;
ListNode slow = head;
ListNode fast = head;
// Find middle
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// Reverse second half
ListNode secondHalf = reverse(slow);
// Compare both halves
ListNode firstHalf = head;
while (secondHalf != null) {
if (secondHalf.val != firstHalf.val) {
return false;
}
secondHalf = secondHalf.next;
firstHalf = firstHalf.next;
}
return true;
}
}
🔍 Dry Run (Quick Summary)
Example:
1 → 2 → 2 → 1
- Middle found
- Second half reversed
- Compare values one by one
Result → Palindrome ✅
⏱️ Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
⚠️ Edge Cases
- Single node
- Two nodes
- Odd length list
- Even length list
💡 Key Takeaways
- Fast & slow pointer technique is essential
- Reversing linked list is a reusable pattern
- Helps optimize space complexity
🚀 Final Thoughts
This is a classic interview problem combining multiple linked list techniques.
Make sure you understand:
- Pointer movement
- Reversal logic
- Comparison step
👉 For full clarity, don’t skip the video explanation above.
