Cadeia que se lê igual ao contrário
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
Comparar o primeiro valor com o último é fácil em um array, mas uma lista simplesmente encadeada não pode ser percorrida de trás para a frente. E se a metade de trás apontasse no sentido contrário?
Mova um ponteiro lento um passo e um ponteiro rápido dois passos por vez. Quando o rápido acabar, o lento estará no início da metade de trás.
Inverta a metade de trás in-place, percorra-a ao lado da metade da frente comparando os valores e depois inverta-a de novo para restaurar a lista.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- the list has between 1 and 10⁵ nodes
- each node holds a digit
Solução
Verificar um palíndromo é comparar o i-ésimo valor a partir da frente com o i-ésimo valor a partir do fim, e o único obstáculo é que o fim de uma lista simplesmente encadeada não pode ser percorrido ao contrário. Ponteiros rápido e lento (fast and slow pointers) encontram o meio em uma passada: quando o ponteiro rápido acaba, o lento está no primeiro nó da metade de trás (o próprio nó do meio, se o tamanho for ímpar). Inverter a lista a partir dali torna a metade de trás legível do último nó para dentro, então dois ponteiros podem compará-la com a metade da frente. A comparação para quando a metade invertida acaba, o que também ignora um nó do meio solitário. Inverter essa metade uma segunda vez coloca todas as ligações de volta. O tempo é O(n) e o espaço extra é O(1).
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return Node(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def reverse(node):
prev = None
while node:
node.next, prev, node = prev, node, node.next
return prev
def is_palindrome(head):
slow = fast = head
while fast and fast.next: # slow ends at the back half
slow, fast = slow.next, fast.next.next
tail = reverse(slow)
left, right, same = head, tail, True
while right:
if left.val != right.val:
same = False
break
left, right = left.next, right.next
reverse(tail) # restore the original links
return same
print(is_palindrome(build([1, 2, 2, 1]))) # -> True
print(is_palindrome(build([1, 2]))) # -> False
print(is_palindrome(build([7]))) # -> True
chain = build([1, 2, 3, 2, 1])
print(is_palindrome(chain), dump(chain)) # -> True [1, 2, 3, 2, 1]Travou na ideia, e não no código? Ponteiros rápido e lento explica isso.