Palindrome Linked List
Você recebe uma lista simplesmente encadeada armazenada em dois arrays de mesmo tamanho. O nó i contém o valor values[i] e aponta para o nó next[i]; -1 encerra a lista, e o nó inicial é o nó 0. Os nós não estão armazenados na ordem da lista, então siga os ponteiros.
Retorne true se os valores lidos do nó inicial até o final forem iguais aos valores lidos do final de volta ao nó inicial, e false caso contrário.
Função
- nextinteger-array
- o índice do nó ao qual cada nó está conectado, ou -1 para o último nó
- valuesinteger-array
- o valor armazenado por cada nó
- Retornaboolean
- verdadeiro se a lista for lida da mesma forma nas duas direções
Restrições
1 ≤ L ≤ 5000, em queLé o comprimento denexte devalues.-100 ≤ values[i] ≤ 100- Cada
next[i]é-1ou um índice de nó de0aL-1. - Começando no nó
0, a lista visita cada nó exatamente uma vez e então chega a-1. Não há ciclo.
Exemplos
- Entrada
- next = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
- Saída
- true
- Explicação
- Os links visitam os nós
0, 4, 1, 3, 2, então a lista é3, 1, 4, 1, 3. Os dois 3 correspondem, os dois 1 correspondem, e o4no meio não tem um par para comparar.
- Entrada
- next = [2, -1, 3, 1]values = [4, 4, 9, 9]
- Saída
- true
- Explicação
- A lista visita os nós
0, 2, 3, 1e lê4, 9, 9, 4, da mesma forma nos dois sentidos.
- Entrada
- next = [2, -1, 1]values = [1, 2, 1]
- Saída
- false
- Explicação
- O array
valuesé[1, 2, 1], mas a lista visita os nós0, 2, 1e lê1, 1, 2. Invertida, ela fica2, 1, 1, então a resposta éfalse.
Para ir além
Você consegue fazer isso em O(L) tempo com O(1) de memória extra?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Uma verificação de palíndromo compara o primeiro valor com o último, o segundo com o penúltimo e assim por diante. Em uma lista simplesmente encadeada, você só pode avançar. O que permitiria acessar o final?
Copiar os valores para um array na ordem da lista funciona, mas consome
O(L)de memória. Sem a cópia, a segunda metade precisa ser percorrida de trás para frente. Alterar seus links pode tornar isso possível.Encontre o meio com dois ponteiros:
fastavança dois nós cada vez queslowavança um. Quandofastnão puder avançar mais,slowestará no fim da primeira metade. Inverta os nós apósslow, depois percorra a lista a partir do início e do antigo último nó ao mesmo tempo e compare.
Solução
Uma verificação de palíndromo compara cada valor com seu correspondente espelhado da outra extremidade. Uma lista simplesmente encadeada só percorre os elementos para a frente, então a parte difícil é ler a metade de trás na ordem inversa. Uma cópia em um array faz isso usando O(L) de memória, em que L é o número de nós; inverter os links da segunda metade faz isso usando O(1).
Copie os valores para um array
Intuição
Um ponteiro aqui é um índice de nó, e avançar é node = next[node]. Percorra a lista uma vez e copie cada valor para um array, que você pode ler pelas duas extremidades. Compare o primeiro e o último valores, mova os dois índices em direção ao meio e retorne false se houver alguma divergência. Com um comprimento ímpar, o valor do meio é seu próprio par.
Todos os valores precisam ser lidos, então O(L) de tempo é o melhor possível. O custo é de L inteiros extras.
Algoritmo
- Percorra do nó
0até-1e acrescente cadavalues[node]a um array. - Defina
i = 0ejcomo o último índice. - Enquanto
i < j, retornefalsese os dois valores forem diferentes; caso contrário, incrementeie decrementej. - Retorne
true.
def isPalindrome(next, values):
# Write the values out in list order.
seq = []
node = 0
while node != -1:
seq.append(values[node])
node = next[node]
# Compare from both ends toward the middle.
i = 0
j = len(seq) - 1
while i < j:
if seq[i] != seq[j]:
return False
i += 1
j -= 1
return TrueInverta a segunda metade no próprio lugar
Intuição
Inverta os links da segunda metade em vez de copiá-la: assim, percorrer a partir do antigo último nó leva em direção ao meio. Para encontrar o meio, avance fast dois links para cada link que slow avança, enquanto fast tiver dois links à frente. slow para no último nó da primeira metade, o nó do meio quando L é ímpar. No primeiro exemplo, slow percorre 0 → 4 → 1, enquanto fast percorre 0 → 1 → 2, então slow para no 4.
Inverta os nós depois de slow e, em seguida, percorra left a partir da cabeça e right a partir da metade invertida ao mesmo tempo: 3 com 3, depois 1 com 1. A metade invertida nunca é mais longa do que a primeira metade, então parar quando right terminar compara exatamente os pares relevantes. Cada etapa percorre no máximo L nós e armazena alguns números inteiros. Em R, alterar next_ copia o vetor uma vez, então R usa O(L) de memória.
Algoritmo
- Defina
slow = fast = 0. Enquantonext[fast]enext[next[fast]]não forem ambos-1, avanceslowum elo efastdois. - Inverta a lista que começa em
next[slow]: para cada nó, salve seu elo, aponte-o parapreve, em seguida, avancepreve o nó. - Defina
left = 0eright = prev, o início da metade invertida. - Enquanto
right != -1, retornefalsese houver uma divergência; caso contrário, avance os dois ponteiros um elo. - Retorne
true.
def isPalindrome(next, values):
# Find the middle: fast moves two links for every one link slow moves.
slow = 0
fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
# slow is the last node of the first half (the middle node when the length is odd).
# Reverse the links of the second half.
prev = -1
node = next[slow]
while node != -1:
after = next[node]
next[node] = prev
prev = node
node = after
# prev is the old last node, now the head of the reversed half.
left = 0
right = prev
while right != -1:
if values[left] != values[right]:
return False
left = next[left]
right = next[right]
return True
Armadilhas e casos extremos
- Verificar os arrays em vez da lista. No terceiro exemplo,
valuesé[1, 2, 1], mas a lista mostra1, 1, 2. - Testar apenas
next[fast] != -1.fastpode então avançar para-1e lernext[-1], que está fora dos limites na maioria das linguagens e aponta silenciosamente para a última entrada em Python e Ruby. - Comparar até
leftterminar, em vez deright. O nó do meio ainda aponta para a antiga segunda metade, então o percurso a partir da cabeça é o mais longo. - Substituir
next[node]durante a inversão antes de salvá-lo, o que faz o restante da lista ser perdido. - Em Lua e R, onde os arrays começam em 1, ler
next[node]usando um ID de nó baseado em 0. Leianext[node + 1].
Perguntas frequentes3
Qual é a complexidade de tempo da verificação de palíndromo em uma lista encadeada?
Todas as abordagens são O(L) para uma lista de L nós, porque cada valor precisa ser comparado. Copiar os valores para um array ou colocá-los em uma pilha usa O(L) de memória extra; inverter a segunda metade no próprio lugar usa O(1).
Como os ponteiros rápido e lento encontram o meio de uma lista encadeada?
Ambos começam na cabeça, e o ponteiro rápido dá dois passos para cada passo do ponteiro lento. Quando o ponteiro rápido chega ao fim, ele percorreu toda a lista, e o ponteiro lento, metade dela.
Inverter metade da lista destrói a entrada?
Sim, ele altera os links da segunda metade e, na maioria das linguagens, esse array pertence ao próprio chamador. Se a lista ainda for necessária, termine a comparação sem retornar antes e, em seguida, inverta essa metade novamente. O nó do meio ainda aponta para o primeiro nó da metade, então a lista fica inteira novamente usando memória extra O(1).
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def isPalindrome(next, values):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
next = [4, 3, -1, 2, 1] values = [3, 4, 3, 1, 1]
Saída Esperada
true