Remove Nth Node From End of 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 a cabeça é o nó 0. Os nós não estão armazenados na ordem da lista, então siga os links.
Remova o n-ésimo nó contado a partir do fim da lista, sendo o último nó o 1º a partir do fim. Retorne os valores dos nós restantes, na ordem da lista.
Função
- valuesinteger-array
- o valor armazenado por cada nó
- nextinteger-array
- o índice do nó ao qual cada nó está ligado, ou -1 para o último nó
- ninteger
- qual nó remover, contando a partir do final, em que 1 é o último nó
- Retornainteger-array
- os valores restantes na ordem da lista, vazia quando o único nó é removido
Restrições
1 ≤ L ≤ 5000, ondeLé o comprimento devaluese denext.-100 ≤ values[i] ≤ 1001 ≤ n ≤ L- Cada
next[i]é-1ou um índice de nó de0aL-1. - A partir do nó
0, a lista visita cada nó exatamente uma vez e então chega a-1. Não há ciclo.
Exemplos
- Entrada
- values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
- Saída
- [5, 2, 6, 7]
- Explicação
- Seguindo os links a partir do nó
0, visitamos os nós0, 2, 4, 1, 3, então a lista contém5, 2, 6, 9, 7. O 2º nó a partir do fim é o nó1, com valor9, e sem ele a lista contém5, 2, 6, 7. A entrada do arrayvalues[5-2] = 7é o último nó, não aquele que deve ser removido.
- Entrada
- values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
- Saída
- [20, 30, 40]
- Explicação
- Quatro nós e
n = 4: o 4º nó a partir do fim é o início. A lista agora começa no nó1e contém20, 30, 40.
- Entrada
- values = [42]next = [-1]n = 1
- Saída
- []
- Explicação
- O único nó é tanto o primeiro quanto o último nó. Removê-lo deixa uma lista vazia, então a resposta é
[].
+14 testes ocultos ao enviar
Para ir além
Você consegue encontrar e desvincular o nó em uma única passagem, sem contar o comprimento primeiro?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Uma lista só percorre os elementos para a frente, e o nó é definido pela sua distância até o fim. Se você soubesse o comprimento
L, em que posição a partir do início ele estaria? E o link de qual nó você precisa alterar para removê-lo?Você pode medir a distância até o fim sem saber o comprimento. Coloque um ponteiro
nnós à frente do outro e mova-os juntos. Quando o ponteiro da frente estiver no último nó, o de trás estará logo antes do nó a ser removido.Mova
fastpara frentenvezes. Se agora ele for-1, o nó a ser removido é o primeiro, então a lista começa emnext[0]. Caso contrário, movaslowefastjuntos enquantonext[fast] != -1, depois definanext[slow] = next[next[slow]]. Percorra a lista a partir do início e reúna os valores.
Solução
O alvo é definido pela distância em relação ao fim, mas uma lista simplesmente encadeada só permite avançar, e você só descobre onde fica o fim quando chega lá. Remover um nó também significa estar no nó anterior a ele, porque é o link desse nó que muda. Você pode copiar a lista para um array ou contá-la e percorrê-la novamente. A solução clássica mantém dois ponteiros separados por n links, de modo que, quando o ponteiro da frente chega ao último nó, o de trás fica logo antes do alvo. Abaixo, L é o número de nós.
Copie os valores para um array
Intuição
Neste problema, um ponteiro é um índice de nó. Avançar é node = next[node], e chegar a -1 significa que você passou do fim. No primeiro exemplo, o percurso a partir do nó 0 segue 0 → 2 → 4 → 1 → 3 → -1.
Contar a partir do fim é difícil apenas porque uma lista não tem posições. Então, atribua posições a ela: percorra a lista uma vez e acrescente cada valor a um array. No primeiro exemplo, esse array é [5, 2, 6, 9, 7]. Em um array com L valores, o último fica no índice L-1, então o n-ésimo a partir do fim fica no índice L-n. Aqui, isso é 5-2 = 3, o 9. Exclua-o e retorne [5, 2, 6, 7].
Isso está correto e leva O(L) de tempo, mas copia a lista inteira e não altera nenhum link. O objetivo do problema é editar a própria lista, usando O(1) de memória extra, como fazem as próximas duas abordagens.
Algoritmo
- Comece com um array vazio e
node = 0. - Enquanto
nodenão for-1, acrescentevalues[node]e avance paranext[node]. - Exclua a entrada no índice
length - n. - Retorne o array.
def removeNthFromEnd(values, next, n):
# Write the values out in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Counting from the end, the n-th value sits at index len(order) - n.
del order[len(order) - n]
return orderConte os nós e, em seguida, desvincule-os
Intuição
Para remover um nó de uma lista, você altera o link do nó anterior a ele para que ele o pule: next[prev] = next[next[prev]]. O nó removido continua nos arrays, mas nenhum percurso a partir da cabeça o alcança novamente.
Então encontre prev. Conte os nós em um primeiro percurso. Contando a cabeça como posição 0, o alvo fica na posição L-n e o nó anterior a ele na posição L-n-1, que você alcança a partir da cabeça em L-n-1 passos. No primeiro exemplo, L = 5 e n = 2: dois passos, 0 → 2 → 4, levam você ao nó 4, que aponta para o nó 1, o 9. Definir next[4] = next[1] = 3 faz a lista ficar 5, 2, 6, 7.
Há um caso em que não existe nó anterior ao alvo: n = L, quando o alvo é a cabeça. Nesse caso, não é necessário religar nada. A lista começa em next[0] em vez de 0, como no segundo exemplo. Depois, percorra a lista a partir da cabeça para coletar a resposta. Dois percursos pela lista custam cerca de 2L movimentos, e a memória além da resposta é de alguns números inteiros.
Algoritmo
- Percorra do nó
0até-1e conte os nós comoL. - Se
n == L, a nova cabeça énext[0]. - Caso contrário, comece com
prevno nó0e avanceL-n-1vezes; em seguida, definanext[prev] = next[next[prev]]. - Percorra a partir da cabeça e colete
values[node]na ordem.
def removeNthFromEnd(values, next, n):
# First pass: count the nodes.
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
head = 0
if n == length:
# The node to remove is the head, so the list starts at its second node.
head = next[0]
else:
# Second pass: stop on the node just before position length - n.
prev = 0
for _ in range(length - n - 1):
prev = next[prev]
next[prev] = next[next[prev]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return resultDois ponteiros separados por n links
Intuição
Você pode medir “n a partir do fim” sem saber L. Avance fast n links enquanto slow espera no início. Em seguida, avance ambos um link por vez. A distância continua sendo n, então, quando fast estiver no último nó (next[fast] == -1, posição L-1), slow estará na posição L-1-n: o nó imediatamente anterior ao alvo. Um next[slow] = next[next[slow]] remove o alvo.
Acompanhe o primeiro exemplo. fast dá dois passos, 0 → 2 → 4. Agora ambos avançam: slow vai para 2 enquanto fast vai para 1, depois slow vai para 4 enquanto fast vai para 3. O nó 3 é o último, então você para. next[4] é o nó 1, o 9, e definir next[4] = next[1] = 3 o remove.
O caso da cabeça aparece naturalmente. Como n ≤ L, fast chega a -1 durante o avanço inicial somente quando n = L, e é exatamente nesse caso que a cabeça é o alvo. Com objetos de nó, você colocaria um nó fictício antes da cabeça para eliminar esse caso; aqui, a verificação fast == -1 faz o mesmo. Encontrar e remover o nó exige uma passagem. Escrever a resposta exige mais uma percorrida, necessária em qualquer abordagem.
Algoritmo
- Defina
fast = 0e avance-onvezes comfast = next[fast]. - Se
fast == -1, a cabeça é o alvo: a nova cabeça énext[0]. - Caso contrário, defina
slow = 0e avance ambos enquantonext[fast] != -1. - Defina
next[slow] = next[next[slow]]. - Percorra a partir da cabeça e colete
values[node]em ordem.
def removeNthFromEnd(values, next, n):
# Send fast n links ahead of slow.
fast = 0
for _ in range(n):
fast = next[fast]
head = 0
if fast == -1:
# Fast fell off the end, so the list has exactly n nodes: remove the head.
head = next[0]
else:
# Move both, keeping the gap. When fast stands on the last node,
# slow stands just before the node to remove.
slow = 0
while next[fast] != -1:
slow = next[slow]
fast = next[fast]
next[slow] = next[next[slow]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
Armadilhas e casos extremos
A maioria das respostas erradas se deve ao ponto em que o seguidor para e ao caso em que a cabeça é removida.
- Remover a entrada no índice
L-ndo array. Os nós não são armazenados na ordem da lista, então esse índice geralmente corresponde a outro nó. No primeiro exemplo,values[3] = 7é o último nó, não o9. - Parar quando
fast == -1em vez de quandonext[fast] == -1. Isso fazslowavançar um passo a mais, até o próprio alvo, e em uma lista simplesmente encadeada não é possível desvincular um nó a partir dele mesmo. - Esquecer o caso da cabeça. Quando
n = L,fasté-1depois do avanço inicial a partir da cabeça, e lernext[fast]causa um erro na maioria das linguagens. Python lênext[-1]sem reclamar e retorna uma lista errada, o que é mais difícil de perceber. - Desvincular usando
next[slow] = next[slow] + 1ouslow + 2. Os nós vizinhos na lista não são vizinhos nos arrays; o único caminho até o nó seguinte ao alvo énext[next[slow]]. - Coletar a resposta começando no nó
0depois que a cabeça foi removida. Comece a percorrida final pela nova cabeça. - Esquecer o deslocamento em Lua e R, nas quais os arrays começam em 1. Mantenha os índices dos nós baseados em 0 e leia
next[node + 1]. Ruby e R reservam a palavranext, então, nos códigos iniciais, o parâmetro recebe o nomenext_.
Perguntas frequentes4
Como remover o n-ésimo nó a partir do fim de uma lista encadeada em uma única passagem?
Use dois ponteiros com uma distância de n. Avance o primeiro n nós e, em seguida, mova os dois juntos até que o primeiro esteja no último nó. O segundo estará imediatamente antes do nó a ser removido, então faça seu link apontar para além desse nó. Se o primeiro ponteiro ultrapassar o fim da lista durante seu avanço inicial, o nó a ser removido é o início da lista.
Por que as soluções para esse problema usam um nó fictício?
Remover um nó significa alterar o link do nó anterior a ele, e o início da lista não tem nenhum nó antes dele. Um nó fictício colocado antes do início dá a todos os nós, inclusive ao início, um predecessor, então uma única linha para desvincular cobre todos os casos. A resposta começa, então, no próximo nó do nó fictício. Verificar se o ponteiro inicial ultrapassou o fim da lista após n etapas trata do mesmo caso sem o nó extra.
Qual é a complexidade de tempo e espaço para remover o n-ésimo nó a partir do final?
Uma lista com L nós leva O(L) tempo, pois você precisa chegar ao final para saber onde está o alvo. Tanto a contagem prévia quanto o método de dois ponteiros usam O(1) de memória extra. Copiar os valores para um array usa O(L).
A solução com dois ponteiros é mais rápida do que contar o comprimento primeiro?
Não muito: ambos são O(L), e os dois ponteiros juntos ainda fazem aproximadamente tantos movimentos quanto duas passagens fariam. O verdadeiro ganho é que você nunca precisa saber o comprimento de antemão, então o método também funciona quando a lista chega como um fluxo que você só pode ler uma vez. É essa única passagem que os entrevistadores costumam pedir.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def removeNthFromEnd(values, next, n):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
values = [5, 9, 2, 7, 6] next = [2, 3, 4, -1, 1] n = 2
Esperado
[5, 2, 6, 7]