3

quería implementar un método el cual elimine un nodo entremedio, es decir, el método debe eliminar los nodos que se encuentran en las posiciones intermedias y el cual el valor sea igual al pasado como segundo parámetro

class LinkedList:
    """
    Lista simplemente encadenada    

    Atributos
    ---------
    __first: (Node) referencia al primer nodo de la lista
    __len  : (int) almacena el número de elementos de la lista        

    Clases
    ------
    LinkedList.Node: clase para representar los nodos de la lista encadenada
    """

    def __init__(self):      
        self.__first = None
        self.__len = 0        

    def __len__(self):
        return self.__len    

    class Node:
        def __init__(self, value, next_node = None):
            self.value = value
            self.next_node = next_node        

    # NO MODIFIQUE código que está por encima

Método mencionado anteriormente

 def eliminar_nodo(self, value):

        current_node = self.__first
        prev_node = current_node

        while current_node is not None:
            if current_node.value == value:
                if current_node == self.__first:
                    self.__first = self.__first.next_node
                    self.__len -= 1
                else:
                    prev_node.next_node = current_node.next_node
                    self.__len -= 1

            prev_node = current_node
            current_node = current_node.next_node

El problema viene cuando intento borrar un elemento intermedio repetido contiguo.

Lista original: [10, 14, 16, 16, 16, 19, 25]
nodo a eliminar: 16
resultado: [10, 14, 16, 19, 25]
output esperado: [10, 14, 19, 25]

1 respuesta 1

1

El error se debe a que cuando eliminas un nodo intermedio no puedes hace que prev_node sea el nodo eliminado en la siguiente iteración, si current_node se ha eliminado prev_node debe seguir apuntando al nodo anterior al eliminado en la siguiente iteración.

Lo que está pasando ahora:

introducir la descripción de la imagen aquí

El verde es current_node y el azul prev_node. El último esquema el resultado final.

Lo que debería pasar:

introducir la descripción de la imagen aquí

Por lo tanto el código debería ser:

def eliminar_nodo(self, value):
    current_node = self.__first
    prev_node = current_node

    while current_node is not None:
        if current_node.value == value:
            if current_node is self.__first:
                self.__first = self.__first.next_node
                self.__len -= 1
            else:
                prev_node.next_node = current_node.next_node
                self.__len -= 1
        else:  # Solo si no se eliminó el nodo prev_node debe cambiar
            prev_node = current_node 
        current_node = current_node.next_node
1

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.