Next palindromic number
Note: Minor change to the algorithm after I found a scenario it didn't cover

This is more of a mathematical problem than a programming one. After some thinking and experimentation, I've come up with an algorithm that can solve this in O(n), where n is the number of digits in the starting number. The basic principle is that we first break down the number into an array of digits, then start at the two ends and work our way inward to the middle, trying to set each pair of digits to the lower one, or as close to the lower one, in as many places as possible.

When examining a pair of digits, we always override the lower-order digit with the higher-order one. If the lower-order digit is greater than the higher-order one, it means the value of our number has reduced as a result of the override, so we set a carry flag. This carry flag will cause the next digit we measured from the lower end of the number (i.e. the lower-order one if we're less than halfway through the number, and the higher-order one if we're more than halfway through) to increment by one before the override is made. If this incrementation causes the digit to "overflow" into 10, we immediately set the digit to 0, set the carry flag to true, and proceed to the next digit.

function nextPalindrome(n) {
    let digits = [];
    let m = n;
    while (m &gt; 0) {
        digits.unshift(m % 10);
        m = Math.trunc(m / 10);
    }

    let carryFlag = false;
    let midPoint = Math.floor(digits.length / 2);

    for (let i = 0; i &lt; digits.length; i++) {
        let copyFrom = digits[i];
        let copyTo = digits[digits.length - 1 - i] + carryFlag;
        if (copyTo === 10) {
            digits[digits.length - 1 - i] = 0;
            carryFlag = true;
        }
        else {
            let digit = (i &lt; midPoint) ? copyFrom : copyTo;
            carryFlag = copyTo &gt; digit;
            digits[i] = digits[digits.length - 1 - i] = digit;
        }
    }

    return digits.reduce((acc, next) =&gt; 10 * acc + next, 0);
}


I don't have a pure mathematical proof detailed, but it seems to work. Please feel free to test it (especially with edge cases) and comment if something's wrong.