Eliminar los nodos con un valor
La misión
Problema
Dada la cabeza de una lista simplemente enlazada y un valor objetivo, elimina cada nodo que guarde ese valor y devuelve la cabeza de lo que queda. Los nodos se desenlazan en lugar de copiarse a una lista nueva, y los nodos que sobreviven conservan su orden original. El resultado puede quedar vacío.
Ejemplos
Input: head = 1 -> 2 -> 6 -> 3 -> 6, target = 6
Output: 1 -> 2 -> 3
Input: head = 7 -> 7 -> 7, target = 7
Output: empty
Por qué: caso límite: todos los nodos coinciden y la lista se vacía
Input: head = empty, target = 1
Output: empty
Por qué: caso límite: no hay nada que eliminar
Pistas
0 / 3
Eliminar un nodo significa cambiar lo que apunta a él, así que el nodo sobre el que estás parado nunca es el que puedes desenganchar.
Párate en el nodo anterior al candidato e inspecciona su sucesor. La cabeza no tiene predecesor, y ese es el único caso que necesitaría su propia rama, a menos que te inventes uno.
Coloca un nodo descartable delante de la cabeza para que cada nodo real tenga un predecesor. Recorre con un puntero que inspecciona el nodo siguiente: desengánchalo cuando coincida y quédate donde estás, porque el nuevo sucesor también hay que inspeccionarlo; avanza solo cuando no coincida.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Solución
Un nodo ficticio (dummy node) colocado antes de la cabeza le da un predecesor a cada nodo real, así que eliminar el primer nodo usa exactamente el mismo reenlace que eliminar cualquier otro. El puntero que recorre inspecciona a su sucesor y no a sí mismo, y después de desenganchar un nodo se queda a propósito donde está, porque el nodo que se deslizó a ese lugar todavía no se inspeccionó. Avanzar después de desenganchar es el error clásico aquí, ya que se salta coincidencias consecutivas. El tiempo es O(n) y el espacio es 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))) # -> []¿Lo que te frena es la idea y no el código? Inserción y eliminación lo explica.