Pular para o conteúdo

Cadeia que se lê igual ao contrário

Fácil#fast-slow-pointers#in-place-reversal~20 min

A missão

Problema

Dado o head de uma lista simplesmente encadeada de dígitos, retorne True se os valores formarem a mesma sequência lidos da frente para trás e de trás para a frente. A lista tem entre 1 e 100.000 nós. Tente atingir tempo O(n) e O(1) de memória extra, o que descarta copiar os valores para uma lista do Python, e deixe a lista no seu formato original quando terminar.

Exemplos

Input:  1 -> 2 -> 2 -> 1
Output: True
Input:  1 -> 2
Output: False
Input:  7
Output: True
Por quê: edge case: um único nó é um palíndromo

Dicas

0 / 3

Tempo-alvo
O(n)
Espaço-alvo
O(1)

Restrições

  • the list has between 1 and 10⁵ nodes
  • each node holds a digit

Travou na ideia, e não no código? Ponteiros rápido e lento explica isso.

Python 3Ctrl+Enter executa