Como saber se uma lista encadeada é um palíndromo?

Estava resolvendo alguns desafios do LeetCode e cheguei no Palindrome Linked List, que consiste em descobrir se uma lista encadeada é um palíndromo.

Caso você não saiba, palíndromo é uma frase ou palavra que se pode ler, indiferentemente, da esquerda para a direita ou vice-versa.

Por exemplo, a palavra reviver. Se você a ler começando pelo começo e for até o final, será a mesma coisa que a ler começando pelo final e indo até o começo. O mesmo ocorre com as palavras ana e ovo.

No caso do desafio, a lista poderia ser considerada um palíndromo se os valores lidos da esquerda para a direita fossem iguais da direita para esquerda.

O exemplo dado no desafio é:

ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}

Ou seja, os valores dessa lista encadeada são 1 2 2 1, que consiste em um palíndromo.

Um jeito bem famoso de resolver problemas com palíndromos em programação é com a estratégia de recursão e, no meu caso, é a estratégia preferida.

Entretanto, eu tentei resolver o desafio com recursão e deu um erro de timeout quando a lista tinha mais de 500 elementos.

Por isso, a estratégia que eu desenvolvi foi de percorrer toda a lista encadeada e criar um array com o node atual na chave val, ou seja, criar um array com todos os elementos da lista.

Com o array de N elementos criado, basta iterar sobre os N / 2 elementos e ver se o começo e o final convergem.

    def isPalindrome(self, head):
        node = head
        values = [node.val]

        while node.next:
            node = node.next
            values.append(node.val)

        size = len(values)

        for i in range(size // 2):
            if values[i] != values[size - i - 1]:
                return False

        return True

Esse algoritmo tem complexidade O(n), já que precisa iterar por todos os itens da lista encadeada e depois iterar pelos N / 2 elementos do array.