186. Palindrome Linked List

Find the middle with slow/fast pointers, reverse the second half in place, then compare it against the first half node by node — O(1) extra space.

Reverse half, then compare

1. Find the middle with slow/fast pointers.
2. Reverse the list from the middle onward.
3. Compare the first half with the reversed second half; any mismatch means not a palindrome.

slow = middle via fast/slow
prev = reverse(slow)
left, right = head, prev
while right: if left.val != right.val: return False; advance both
return True

Worked example

[1,2,2,1] → second half reversed is [1,2], matches first half → true.

Complexity

• Time: O(n).
• Space: O(1).

class 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;
    }
}