9. Palindrome Number

Reverse only the second half of the number and compare it to the first half — no string conversion, and no risk of integer overflow from reversing the whole number.

Idea

We could reverse the whole number and compare, but that can overflow for large inputs. Instead, reverse only the back half of the digits and compare it against the front half. When the reversed back half becomes as large as (or larger than) the remaining front, we've processed half the digits and can stop.

Two quick rejections first: any negative number can't be a palindrome (the - sign), and any nonzero number ending in 0 can't be one either (it would have to start with 0).

Algorithm

1. If x < 0, or (x ends in 0 and x != 0), return false.
2. Build rev from the trailing digits of x: while x > rev, do rev = rev * 10 + x % 10 and x //= 10.
3. When the loop ends, x holds the front half and rev the reversed back half. It's a palindrome if x == rev (even digit count) or x == rev // 10 (odd digit count — drop the middle digit).

Worked example: x = 1221

Even number of digits → compare x == rev → 12 == 12 → true.

For x = 12321 (odd): loop stops with x = 12, rev = 123; x == rev // 10 → 12 == 12 → true (the middle 3 is ignored).

Complexity

• Time: O(log₁₀ x) — we process half the digits.
• Space: O(1).

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int rev = 0;
        while (x > rev) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return x == rev || x == rev / 10;
    }
}