Definition
- In-place palindrome check – determines if a linked list reads the same forward and backward using O(1) space.
- Step 1 – find the middle with fast-slow pointers.
- Step 2 – reverse the second half using the three-pointer reversal.
- Step 3 – compare first half and reversed second half node by node.
- Step 4 – reverse the second half back to restore the original list.
- Complexity – O(n) time, O(1) extra space.
At the National Bank of India, Priya's cheque has a security code printed as a chain of digits that must be a mirror: the same read left-to-right and right-to-left. A clerk finds the middle, flips the right half around, compares digit by digit, then flips it back so the cheque is unchanged.
Understanding the Concepts
What is the problem?
Given the head of a singly linked list, determine whether it reads the same forwards and backwards. Solve it in O(n) time and O(1) extra space, and restore the list afterward.
At the National Bank of India, premium cheques carry a mirror security code that the system verifies on each deposit.
What is the naive approach?
Copy all values into an ArrayList and check with two pointers from both ends. This is simple but uses O(n) extra space.
List<Integer> values = new ArrayList<>();
ListNode curr = head;
while (curr != null) {
values.add(curr.val);
curr = curr.next;
}
int left = 0, right = values.size() - 1;
while (left < right) {
if (!values.get(left).equals(values.get(right))) return false;
left++;
right--;
}
return true;
How does the four-step in-place approach work?
package com.bank.service;
public class PalindromeCheck {
public static boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// Step 1: Find middle
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse second half
ListNode reversedHead = reverse(slow);
ListNode restorePoint = reversedHead;
// Step 3: Compare
ListNode p1 = head;
ListNode p2 = reversedHead;
boolean result = true;
while (p2 != null) {
if (p1.val != p2.val) {
result = false;
break;
}
p1 = p1.next;
p2 = p2.next;
}
// Step 4: Restore
reverse(restorePoint);
return result;
}
private static ListNode reverse(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
public static void main(String[] args) {
ListNode head = new ListNode(1,
new ListNode(2, new ListNode(2, new ListNode(1))));
System.out.println("Palindrome: " + isPalindrome(head));
}
}
Palindrome: true
Why is restoration important?
Reversing the second half mutates the input list. If other code holds a reference to nodes in the list, they see a corrupted structure. Restoring it makes the method side-effect free.
// Without restore: 1 -> 2 -/-> 2 <- 1 (broken)
// With restore: 1 -> 2 -> 2 -> 1 (original)
How does odd length work?
For `1 -> 2 -> 3 -> 2 -> 1`, the slow pointer lands on 3. Reversing from 3 gives `1 -> 2 -> 3`. Comparing: - First half: 1, 2, 3 - Reversed half: 1, 2, 3
All match. The middle node (3) appears in both halves but compares with itself.
Why compare values, not references?
Two different node objects can hold the same value. Using == on object references would fail even when values match. For money amounts, use BigDecimal.compareTo() instead of equals() to handle scale differences.
// Wrong for objects
if (p1.amount == p2.amount) // reference equality, fails
// Correct for BigDecimal
if (p1.amount.compareTo(p2.amount) == 0) // value equality
What is the time and space complexity?
| Approach | Time | Space |
|---|---|---|
| In-place (4 steps) | O(n) | O(1) |
| Array copy | O(n) | O(n) |
| Recursive | O(n) | O(n) stack |
What are common mistakes?
Not saving the reversed head for restoration, making it impossible to reverse back.
// Wrong: reversed head is lost after comparison walk
ListNode rev = reverse(slow);
while (rev != null) { ... } // rev is now null
reverse(rev); // reverses nothing
// Correct: save the head separately
ListNode revHead = reverse(slow);
ListNode walker = revHead;
while (walker != null) { ... }
reverse(revHead); // restores correctly
What are the edge cases?
- Empty list: return true.
- Single node: return true.
- Two identical nodes:
[5, 5]is a palindrome. - Two different nodes:
[5, 7]is not.
What should a senior engineer know?
This problem is a composition of three reusable subroutines: fast-slow middle finding, in-place reversal, and two-pointer comparison. The ability to compose known building blocks into a clean solution is the senior signal.
In concurrent systems, even the brief mutation during the check can be visible to other threads. Use synchronization or copy-based approaches in such contexts.
What are common interview follow-up questions?
- Can you check without modifying the list? (Use the array approach or recursion.)
- What if the list is doubly linked? (Walk from both ends, no reversal needed.)
- What about BigDecimal values? (Use compareTo for value equality.)
Visual Overview
List: 1 -> 2 -> 2 -> 1
Step 1: Find middle
slow: 1 -> 2 -> [2] fast: 1 -> 2 -> null
Step 2: Reverse from slow
Before: 2 -> 1 -> null
After: 1 -> 2 -> null (reversed head = 1)
Step 3: Compare
p1: 1 -> 2 p2: 1 -> 2
1 == 1 ✓ 2 == 2 ✓ p2 null -> PALINDROME
Step 4: Restore
Reverse 1 -> 2 back to 2 -> 1
Original list restored: 1 -> 2 -> 2 -> 1
┌──────────────────────────────────────────────┐ │ In-Place Palindrome Check Flow │ ├──────────────────────────────────────────────┤ │ │ │ 1. Fast-slow -> find middle │ │ │ │ │ ▼ │ │ 2. Reverse second half │ │ │ │ │ ▼ │ │ 3. Compare first half vs reversed half │ │ │ │ │ Match? │ │ Yes: palindrome No: not palindrome │ │ │ │ │ ▼ │ │ 4. Reverse second half again (restore) │ │ │ │ │ ▼ │ │ Return result │ └──────────────────────────────────────────────┘
Key Takeaway
Checking whether a linked list is a palindrome in O(1) space is a four-step in-place technique. Find the middle with fast-slow pointers, reverse the second half, compare both halves node by node, and restore the second half.
The naive approach copies values into an array, which is clear but uses O(n) space. The in-place approach avoids that, which matters for very long lists in memory-sensitive services.
At the National Bank of India, Priya's premium cheque book carries mirror security codes. The verification service runs the four-step check and always restores the list because it is the customer's real stored record, and leaving it reversed would corrupt the data.
One detail to always get right is comparing values, not node references. For money amounts, use BigDecimal.compareTo() so that values like 100 and 100.00 are correctly treated as equal.
Remember one sentence: find the middle, reverse the second half, compare, and restore.
---