Eliminar los nodos duplicados de una lista vinculada sin clasificar

En este artículo, veremos los diferentes enfoques para eliminar los nodos duplicados de la lista vinculada utilizando la programación C ++. Comencemos con una explicación de lo que significan los "nodos duplicados" en una lista vinculada.

Se nos da una lista vinculada sin clasificar en este desafío y se les solicitó eliminar cualquier miembro duplicado de la lista. Usemos algunos ejemplos para intentar comprender el problema.

La lista de enlace sin clasificar es la siguiente:

Los elementos 8, 10 y 9 aparecen más de una vez en la lista vinculada, como se ve en la lista anterior. Esto indica que hay duplicados de 8, 10 y 9 en la lista vinculada que debemos eliminar. La lista vinculada de salida es la siguiente una vez que las entradas duplicadas se eliminan de la lista:

Una manera rápida y fácil de averiguarlo es comparar todos los pares posibles de nodos en la lista para ver si tienen la misma información. Cuando su información coincide, nos deshacemos del segundo nodo eliminándola. Pero este enfoque es más lento.

Es posible una mejor eficiencia usando chava. El objetivo es trabajar a través de la lista proporcionada y agregar cada nodo a un conjunto a medida que avanza. Si el nodo visto actualmente aparece en el conjunto anterior, se puede ignorar de forma segura. Cuando el proceso está completo, la lista ya no contendrá nodos duplicados.

Entendamos cada enfoque en detalle.

Enfoque 1: Uso de dos bucles

Pasos de algoritmo

1. Cree una función de lista vinculada, "createLinkedlist", Que puede crear una lista vinculada.
2. Crear una función llamada "DeletedUplateSnodes"Eso puede eliminar el nodo duplicado de la lista vinculada.
3. Cree dos punteros locales, Ptr1 y Ptr2, dentro del "DeletedUplateSnodes" función.
4. Asignar el PTR1 = nodo de cabeza y ptr2 = nulo Valores, donde PTR1 se usa para rastrear el nodo cuyos duplicados deben verificarse y PTR2 se usa para atravesar cada nodo de la lista vinculada para verificar si algún datos del nodo es el mismo que los datos del nodo PTR1.
5. El puntero de bucle anidado PTR2 continúa atravesando todo el nodo de lista vinculada hasta que encuentre nulo.
6. Si los datos del nodo PTR1 son similares a los datos del nodo PTR2 de bucle anidado, elimine ese nodo de la lista vinculada.
7. Si no, incrementa el Ptr1-> Siguiente y verifique los datos del siguiente nodo para duplicados.
8. Los pasos 4 a 7 se repiten hasta que PTR1 no es igual al nulo, lo que indica que alcanzó el final de la lista vinculada.
9. Finalmente, imprimimos la lista vinculada.
10. Fin del algoritmo.

Implementación del código C ++ (usando dos bucles)

Producción:

Explicación:

Líneas 21 a 52: Creamos una función con el nombre, "CreateLinkedList". Pasamos dos parámetros (un puntero del noto al puntero y un valor) en esa función. Como se muestra en el programa anterior, cada vez que se llama a esta función, primero crea un nuevo nodo con un valor (que pasamos) y una dirección de nodo con un valor nulo.

/* Crear un nuevo nodo*/
Nodo* newnode = new Node ();
Nodo * LastNode = * HeadNode;
newnode-> data = value; / * Agregar los datos */
/* Dirección de este nuevo nodo se mantiene intencionalmente nulo*/
newnode-> next = null;

Luego, se verifica para ver si la referencia del nondo es nula. Si es así, el nodo recién creado se convierte en la cabeza.

/* Comprobación de la referencia del nondo es nula o no.
En caso afirmativo, entonces el nuevo nodo se convertirá en el nodo de cabeza*/
if (*headNode == null)
*headNode = newnode;
devolver;

Si la referencia de HeadNode no es nula, se agrega al últimonode de la lista vinculada. La dirección de este recién creado Newnode se asigna al LastNode para que pueda comenzar a señalar el nuevo NEWNODE recién creado.

/* Si no, entonces este bucle While lo hará
ejecutar y encontrar el dastNode del vinculado
Lista, de modo que el recién creado Newnode agregue en el último*/
while (lastNode-> Siguiente != Nulo)
LastNode = LastNode-> Next;

Ahora, el recién creado Newnode se convierte en el LastNode. Este proceso continúa hasta ese momento en que llamamos a esta función.

Los pasos anteriores crean la lista vinculada según nuestros requisitos. Ahora, eliminamos los nodos duplicados de la lista vinculada.

Líneas 57 a 75: Creamos una función llamada "DeletedUplateSnodes" que acepta un parámetro que es el puntero de nodo de la lista vinculada. Creamos dos variables de nivel local, PTR1 y PTR2, para rastrear la lista vinculada cuando la recorre para conocer los duplicados en la lista vinculada. Inicializamos el PTR1 con el nodo de cabeza ya que este será el bucle superior y el PTR2 con el valor nulo.

ptr1 = headNode;

ptr1: Esta variable está en el bucle exterior y rastrea los elementos cuyos duplicados vamos a verificar.

ptr2: Esta variable está dentro del bucle y continúa verificando los datos de cada nodo para averiguar si coincide con los datos de retención PTR1. Si coincide, sus duplicados se eliminan de la lista vinculada. Esto se verifica y continúa hasta que no alcanza el último nodo cuyo valor es nulo.

Cuando ptr2-> next == null, el bucle anidado y el bucle y el bucle externo aumenta el PTR1 = PTR1-> Siguiente con los siguientes datos de nodo.

Nota: El ptr2 termina cuando el ptr1 el bucle ha terminado porque ptr2 está dentro del bucle ptr1.

Mientras (PTR1 != NULL && PTR1-> Siguiente != Nulo)
ptr2 = ptr1;
mientras (Ptr2-> Siguiente != Nulo)
/* Si se encuentra, el siguiente código se eliminará
Duplicados del nodo*/
if (ptr1-> data == ptr2-> next-> data)
duplicado = ptr2-> next;
ptr2-> next = ptr2-> next-> next;
eliminar (duplicado);
else /* Si no se encuentra, PTR2 se actualizará a
al siguiente nodo*/
ptr2 = ptr2-> next;

ptr1 = ptr1-> next;

Líneas 78 a 84: Esto muestra la lista final vinculada sin ninguna duplicación. En ese caso, pasamos el nodo de cabeza como un parámetro que es la dirección de la lista vinculada.

/* Esta función imprimirá la lista vinculada*/
visualización void (nodo* nodo)
while (nodo-> next)
printf ("%d ->", nodo-> datos);
nodo = nodo-> next;

printf ("%d", nodo-> datos);

Enfoque 2: Método de hash

Pasos de algoritmo

1. Cree una función de lista vinculada, "CreateLinkedList", que puede crear una lista vinculada.
2. Cree una función llamada "DeletedUplateSnodes" que puede eliminar el nodo duplicado de la lista vinculada.
3. Cree dos punteros locales, CurrentNode y AnteriorNode, dentro de la función "DeletedUplateSnodes".
4. Crea un hash sin clasificar dentro del "DeletedUplateDatesNodes".
5. Asigne los valores de CurrentNode = HeadNode y AnteriorNode = NULL donde CurrentNode se usa para rastrear el nodo cuyos duplicados deben verificarse y AnteriorNode se usa para rastrear el nodo anterior del Node de CurrentNode.
6. El bucle while atraviesa todo el nodo de lista vinculada hasta que cotentNode == null.
7. Si los datos de CurrentNode ya están en el conjunto hash, el nodo se elimina.
8. Si no, agrega los datos de ese nodo al conjunto hash.
9. Los pasos 5 a 8 se repiten hasta que elnode Current no sea igual al nulo, lo que indica que alcanzó el final de la lista vinculada.
10. Finalmente, imprimimos la lista vinculada.
11. Fin del algoritmo.

Implementación del código C ++ (usando el método hash)

Producción:

Líneas 26 a 52: Creamos una función con el nombre "CreateLinkedList". En esa función, pasamos dos parámetros (un puntero de nodo al puntero y un valor). Como se muestra en el programa anterior, cada vez que se llama a esta función, primero crea un nuevo nodo con un valor (que pasamos) y una dirección con un valor nulo.

/* Crear un nuevo nodo*/
Nodo* newnode = new Node ();
Nodo * LastNode = * HeadNode;
newnode-> data = value; / * Agregar los datos */
/* Dirección de este nuevo nodo se mantiene intencionalmente nulo*/
newnode-> next = null;

Luego, se verifica para ver si la referencia del nondo es nula. Si es así, el nodo recién creado se convierte en la cabeza.

/* Comprobación de la referencia del nondo es nula o no.
En caso afirmativo, entonces el nuevo nodo se convertirá en el nodo de cabeza*/
if (*headNode == null)
*headNode = newnode;
devolver;

Si la referencia de HeadNode no es nula, se agrega al últimonode de la lista vinculada. La dirección de este recién creado Newnode se asigna al LastNode para que pueda comenzar a señalar el nuevo NEWNODE recién creado.

/* Si no, entonces este bucle While lo hará
ejecutar y encontrar el dastNode del vinculado
Lista, de modo que el recién creado Newnode agregue en el último*/
while (lastNode-> Siguiente != Nulo)
LastNode = LastNode-> Next;

Ahora, el recién creado Newnode se convierte en el LastNode. Este proceso continúa hasta ese momento en que llamamos a esta función.

Los pasos anteriores crean la lista vinculada según nuestros requisitos. Ahora, eliminamos los nodos duplicados de la lista vinculada.

Líneas 57 a 75: Creamos una función llamada "DeletedUplateSnodes" que acepta un parámetro que es el puntero de nodo de la lista vinculada. Creamos un hash de hashset sin clasificar. También creamos dos variables de nivel local, CurrentNode y nodo anterior, Para rastrear la lista vinculada cuando la realizamos para conocer los duplicados en la lista vinculada. Inicializamos elNode CurrentN con el NEGNODE ya que este será el bucle superior y el nodo anterior con el valor nulo.

struct node* currentNode = headNode;
struct node* previonode = null;

CurrentNode: Esta variable está en el bucle exterior y rastrea los elementos cuyos duplicados vamos a verificar.

nodo anterior: Esto maneja el nodo anterior de CurrentNode. Creamos un bucle de tiempo que se ejecuta hasta que CurrentNode no encuentre el valor nulo, lo que significa al final de la lista vinculada. Si los datos de CurrentNode ya están en el mapa hash, asigne el valor del CurrentNode's Siguiente puntero al nodo anterior Siguiente puntero.

AnteriorNode-> next = currentNode-> next;

Si no es así, agregue los datos de CurrentNode al mapa hash y haga nodo anterior igual a la CurrentNode.

demás
picadillo.insertar (CurrentNode-> data);
AnteriorNode = CurrentNode;

Al final, asigne el valor del siguiente puntero del nodo previo al Node CurrentNode.

while (currentNode != Nulo)
/* Si los datos de CurrentNode ya visitaron, entonces esto
El código eliminará ese nodo
*/
if (hash.buscar (currentNode-> data) != hash.fin())
AnteriorNode-> next = currentNode-> next;
eliminar (actualnode);

/*
Si no se visitan los datos de CurrentNode, entonces
insertar en el hash
*/
demás
picadillo.insertar (CurrentNode-> data);
AnteriorNode = CurrentNode;

actualnode = previonode-> next;

Líneas 84 a 90: Esto muestra la lista final vinculada sin ninguna duplicación. En ese caso, pasamos el nodo de cabeza como un parámetro que es la dirección de la lista vinculada.

/* Esta función imprimirá la lista vinculada*/
visualización void (nodo* nodo)
while (nodo-> next)
printf ("%d ->", nodo-> datos);
nodo = nodo-> next;

printf ("%d", nodo-> datos);

Conclusión

En el primer método, para deshacerse de los duplicados, utilizamos dos bucles: un bucle externo que itera sobre la lista vinculada y selecciona un elemento, y un segundo bucle que itera sobre ese elemento para buscar posibles duplicados. Tan pronto como se detecta un duplicado, se elimina de la lista. Este método utiliza un bucle anidado para examinar y eliminar los duplicados de una lista vinculada sin clasificar que aumenta la complejidad del tiempo del proceso. La complejidad del tiempo es o (n²).

En el segundo método, el hashing se puede usar para minimizar la complejidad temporal de eliminar los duplicados de una lista vinculada sin clasificar. En este caso, si el nodo aparece en el hashmap dos veces, es una duplicación y la primera ocurrencia debe eliminarse. Si falta un nodo en el mapa, es porque hay uno nuevo que debe agregarse. Se tarda en promedio en tiempo en repasar una lista vinculada de longitud "n" y verificaciones si sus nodos están en el mapa. La complejidad temporal para buscar un valor en una tabla hash es o (1). Teniendo en cuenta los requisitos previos antes mencionados juntos, la complejidad del tiempo total es o (n).