Approach Summary
Find mid with slow/fast pointers, reverse the second half in-place, compare both halves, then restore the list.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Full Solution & Approach
A linked list cannot be indexed from both ends the way an array can, so the standard approach is to split the list in half, reverse the second half in place, and compare the two halves element by element. First find the middle using the slow-and-fast pointer trick: slow advances one node per step while fast advances two, so when fast reaches the end, slow is at the midpoint. Then reverse the second half starting from slow by walking it with three pointers — prev, cur, and next — flipping each cur.next to prev. Now walk the two halves together: if any pair of values differs, the list is not a palindrome; if the reversed half is fully consumed without a mismatch, it is. The comparison only needs to run until the reversed half runs out, which naturally stops at the middle of an odd-length list. Everything happens in place with no extra array, which is the point of the problem — an O(1)-space answer rather than copying the values into an array and using the array palindrome check.
Finding the middle is one pass, reversing the second half is a second pass over half the nodes, and comparing is a third pass — all O(n). Only pointer variables are used, so O(1) extra space (the reverse modifies the list in place).
Solution Code
Solution
public boolean isPalindrome(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode prev = null;
while (slow != null) {
ListNode nxt = slow.next;
slow.next = prev;
prev = slow;
slow = nxt;
}
ListNode left = head, right = prev;
while (right != null) {
if (left.val != right.val) return false;
left = left.next;
right = right.next;
}
return true;
}bool isPalindrome(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* prev = nullptr;
while (slow) {
ListNode* nxt = slow->next;
slow->next = prev;
prev = slow;
slow = nxt;
}
ListNode *left = head, *right = prev;
while (right) {
if (left->val != right->val) return false;
left = left->next;
right = right->next;
}
return true;
}def is_palindrome(head: Optional[ListNode]) -> bool:
# Find the middle with slow/fast pointers
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse the second half (starting at slow)
prev = None
while slow:
nxt = slow.next
slow.next = prev
prev = slow
slow = nxt
# Compare the two halves
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return Truefunction isPalindrome(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
let prev = null;
while (slow) {
const nxt = slow.next;
slow.next = prev;
prev = slow;
slow = nxt;
}
let left = head, right = prev;
while (right) {
if (left.val !== right.val) return false;
left = left.next;
right = right.next;
}
return true;
}Edge Cases to Watch
- Empty or single-node list — trivially a palindrome
- Even-length list — halves split cleanly at the midpoint
- Odd-length list — the middle node is excluded from the comparison
- All identical values — true even for long lists
Master the Linked List Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Linked List pattern.
How to Recognize This Pattern
- "Check palindrome without extra space"
- Reverse second half → one-pass comparison
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)