Definition
- Palindrome check – determine whether a linked list reads the same forward and backward.
- Step 1 – find the middle using fast-slow pointers.
- Step 2 – reverse the second half in place.
- Step 3 – compare the first half and reversed second half node by node.
- Step 4 – restore the second half by reversing it again (production best practice).
- Complexity – O(n) time, O(1) extra space.
At the National Bank of India, Rajesh has a chain of linked digits forming a cheque security code and wants to know if it reads the same from either end. He finds the middle of the chain, flips the second half around, walks both halves comparing digit by digit, and then flips the second half back to leave the chain unchanged.
Understanding the Concepts
What is the problem?
Given the head of a singly linked list, determine whether it reads the same forward and backward. For example, 1 -> 2 -> 2 -> 1 is a palindrome, but 1 -> 2 -> 3 is not.
At the National Bank of India, premium cheque books have a mirror security code stored as a linked chain of digits.
What is the naive approach?
Copy all values into an ArrayList and check with two pointers from both ends.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class PalindromeNaive {
public static boolean isPalindrome(ListNode head) {
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;
}
}
This is clear but uses O(n) extra space. The in-place approach avoids that.
How does the in-place approach work?
Combine three techniques: find middle, reverse second half, compare, restore.
package com.bank.service;
public class PalindromeLinkedList {
public static 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;
}
// Step 2: Reverse the second half
ListNode secondHalf = reverse(slow);
ListNode secondHalfHead = secondHalf; // save for restore
// Step 3: Compare both halves
ListNode firstHalf = head;
boolean isPalin = true;
while (secondHalf != null) {
if (firstHalf.val != secondHalf.val) {
isPalin = false;
break;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
// Step 4: Restore the second half
reverse(secondHalfHead);
return isPalin;
}
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) {
// Build: 1 -> 2 -> 2 -> 1
ListNode head = new ListNode(1,
new ListNode(2, new ListNode(2, new ListNode(1))));
System.out.println("Is palindrome: " + isPalindrome(head));
}
}
Is palindrome: true
Why restore the list after checking?
Reversing the second half mutates the input list. In a shared or concurrent context, leaving it reversed corrupts the caller's data. Restoring it makes the method side-effect free.
// Before check: 1 -> 2 -> 2 -> 1
// After reverse second half: 1 -> 2 -> 2 <- 1 (broken structure)
// After restore: 1 -> 2 -> 2 -> 1 (original structure)
How does odd length work?
For 1 -> 2 -> 1, the slow pointer lands on the middle node (value 2). The reversed second half is 1 -> 2. Comparing first half 1 -> 2 -> (middle) with reversed half 1 -> 2, the comparison walks until the shorter (reversed) half runs out: 1 == 1, then the reversed pointer is null. Result: palindrome.
What is the time and space complexity?
| Approach | Time | Space |
|---|---|---|
| In-place (find middle, reverse, compare) | O(n) | O(1) |
| Array copy | O(n) | O(n) |
| Recursive | O(n) | O(n) stack |
What are common mistakes?
Forgetting to save the head of the reversed second half before the comparison walk, making it impossible to restore.
// Wrong: lost the reversed head
ListNode reversed = reverse(slow);
while (reversed != null) { ... } // reversed is now null, cannot restore
// Correct: save the head
ListNode reversedHead = reverse(slow);
ListNode walker = reversedHead;
while (walker != null) { ... }
reverse(reversedHead); // restore
What are the edge cases?
- **Empty list**: return true (vacuously a palindrome). - **Single node**: return true. - **Two nodes, same value**: `1 -> 1` is a palindrome. - **Two nodes, different value**: `1 -> 2` is not a palindrome. - **Even length**: both halves are equal size. - **Odd length**: the middle node is skipped in comparison.
What should a senior engineer know?
This problem is a composition of three fundamental techniques: fast-slow pointers, in-place reversal, and two-pointer comparison. Being able to decompose a complex problem into known subroutines and compose them correctly is the senior skill.
In concurrent systems, the restoration step is not optional. Mutating shared data structures without restoration is a production bug.
What are common interview follow-up questions?
- Can you do it without modifying the list? (Use the array copy approach or a recursive approach.)
- What if the values are
BigDecimalamounts? (UsecompareToinstead of==.) - What if the list is doubly linked? (Walk from both ends directly, no reversal needed.)
Visual Overview
List: 1 -> 2 -> 2 -> 1
Step 1: Find middle (slow/fast)
slow: 1 -> 2 -> [2] (lands on second 2)
fast: 1 -> 2 -> null (reached end)
Step 2: Reverse second half starting at slow
Before: ... -> 2 -> 1 -> null
After: null <- 2 <- 1 (reversed head = 1)
Step 3: Compare
First half: 1 -> 2
Reversed half: 1 -> 2
1 == 1 ✓
2 == 2 ✓
Reversed pointer is null -> stop -> PALINDROME
Step 4: Restore second half
Before: null <- 2 <- 1
After: ... -> 2 -> 1 -> null (original order)
┌──────────────────────────────────────────────┐ │ Palindrome Linked List Flow │ ├──────────────────────────────────────────────┤ │ │ │ 1. Fast-slow pointers -> find middle │ │ │ │ │ ▼ │ │ 2. Reverse second half in place │ │ │ │ │ ▼ │ │ 3. Walk first half + reversed half │ │ Compare values node by node │ │ │ │ │ Mismatch? │ │ Yes: NOT palindrome │ │ No: IS palindrome │ │ │ │ │ ▼ │ │ 4. Reverse second half again (restore) │ └──────────────────────────────────────────────┘
Key Takeaway
Checking whether a linked list is a palindrome in constant space combines three fundamental techniques. Find the middle with fast-slow pointers, reverse the second half in place, compare both halves node by node, and restore the second half.
The naive approach copies values into an array and checks with two indices, which is clear but uses O(n) space. The in-place approach avoids that allocation entirely, which matters for long lists in memory-sensitive services.
At the National Bank of India, Rajesh verified symmetric reference codes stored as linked chains of digits. The chains could be long and the service was memory-sensitive, so the in-place approach met the constant-space requirement. The original chain was used by the next step in the flow, so restoring it was not optional.
The senior-level point is the restoration. Reversing the second half mutates the list, so in any shared or concurrent context, restore it afterward or document that the method is destructive. Being able to compose find-middle, reverse, and compare into one clean solution demonstrates production-level thinking.
Remember one sentence: find the middle, reverse the second half, compare node by node, and restore the list.
---