Find next biggest palindrome

Question

I have written a program for the SPOJ PALIN problem:

A positive integer is called a palindrome if its[decimal representation is the same]from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. …

My program does not seem to be fast enough (needs to run between 2s - 9s). One way I have thought of is getting rid of the string based math but when I coded that, it started to fail on specific numbers. Is there a way to optimize this code that I am not seeing?

Code:

from math import ceil


def next_palindrome(n):
    digits = list(str(n))
    length = len(digits)
    mid = length / 2
    rev = int("".join(digits[::-1]))

    if all(d == "9" for d in digits):
        return n + 2
    if length == 1:
        return n + 1

    left = digits[: int(mid)]
    digits[ceil(mid) :] = left[::-1]
    palindrome = int("".join(digits))

    if palindrome > n:
        return palindrome

    if length % 2 != 0:
        mid = int(mid)
        if digits[mid] == "9":
            # return int("".join(digits)) + (11 * (10 * (mid - 1)))
            return int("".join(digits)) + int(f"11{'0' * (mid - 1)}")

        digits[mid] = f"{int(digits[mid])+1}"
        return "".join(digits)

    left_d, right_d = left[-1], digits[ceil(mid) :][0]
    if left_d == "9" and right_d == "9":
        mid = int(mid)
        # return int("".join(digits)) + (11 * (10 * (mid - 2)))
        return int("".join(digits)) + int(f"11{'0' * (mid - 2)}")

    left[-1] = f"{int(left_d) + 1}"
    return "".join(left + left[::-1])

t = int(input())
for i in range(t):
    n = int(input())
    print(next_palindrome(n))

Answer 1

Python strings are already effectively lists of characters. There is no need to convert the string into a list of single character strings. This:

    digits = list(str(n))
    rev = int("".join(digits[::-1]))

could be written simply as this:

    digits = str(n)
    rev = int(digits[::-1])

eliminating the unnecessary join. Similar improvements may be made throughout the code.

---

The real speed up comes from realizing palindromes can be easily enumerated.

The nth even-length palindrome is str(n) + str(n)[::-1]

The nth odd-length palindrome is str(n) + str(n)[-2::-1]

n can be determined from the first half of the digits of the input number. If the generated palindrome is not large enough, generate the n+1-th.