Remover nós com um valor
A missão
Problema
Dado o head de uma lista simplesmente encadeada e um valor-alvo, remova todos os nós que guardam esse valor e retorne o head do que sobrar. Os nós são desligados, em vez de copiados para uma lista nova, e os nós que sobrevivem mantêm a ordem original. O resultado pode ser vazio.
Exemplos
Input: head = 1 -> 2 -> 6 -> 3 -> 6, target = 6
Output: 1 -> 2 -> 3
Input: head = 7 -> 7 -> 7, target = 7
Output: empty
Por quê: edge case: todos os nós correspondem e a lista fica vazia
Input: head = empty, target = 1
Output: empty
Por quê: edge case: não há nada para remover
Dicas
0 / 3
Remover um nó significa mudar o que aponta para ele, então o nó em que você está nunca é o que você consegue desengatar.
Fique no nó antes do candidato e inspecione o sucessor dele. O head não tem antecessor, e esse é o único caso que precisaria de um tratamento especial, a menos que você invente um antecessor.
Coloque um nó descartável na frente do head para que todo nó real tenha um antecessor. Percorra a lista com um ponteiro que inspeciona o próximo nó: desengate-o quando ele corresponder e fique parado, porque o novo sucessor também precisa ser inspecionado, e só avance quando ele não corresponder.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Solução
Um nó descartável colocado antes do head dá a todo nó real um antecessor, então apagar o primeiro nó usa exatamente a mesma religação que apagar qualquer outro. O ponteiro que percorre a lista inspeciona o seu sucessor, e não a si mesmo, e depois de desengatar um nó fica deliberadamente onde está, porque o nó que deslizou para aquela posição ainda não foi inspecionado. Avançar depois de desengatar é o bug clássico aqui, já que isso pula correspondências consecutivas. O tempo é O(n) e o espaço é 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 remove_value(head, target):
dummy = Node(0, head) # lets head removal use the same relink
node = dummy
while node.next:
if node.next.val == target:
node.next = node.next.next # unhook, and do not move on
else:
node = node.next
return dummy.next
print(dump(remove_value(build([1, 2, 6, 3, 6]), 6))) # -> [1, 2, 3]
print(dump(remove_value(build([7, 7, 7]), 7))) # -> []
print(dump(remove_value(build([]), 1))) # -> []Travou na ideia, e não no código? Inserir e remover explica isso.