Dada una lista enlazada ordenada, elimine todos los Nodes que tengan números duplicados (todas las ocurrencias), dejando solo los números que aparecen una vez en la lista original.
Ejemplos:
Input: 23->28->28->35->49->49->53->53 Output: 23->35 Input: 11->11->11->11->75->75 Output: empty List
Tenga en cuenta que esto es diferente de Eliminar duplicados de la lista vinculada
La idea es mantener un puntero (prev) al Node que está justo antes del bloque de Nodes que estamos buscando duplicados. En el primer ejemplo, el puntero anterior apuntaría a 23 mientras buscamos duplicados para el Node 28. Una vez que lleguemos al último Node duplicado con valor 28 ( nómbrelo puntero actual ), podemos hacer que el siguiente campo del Node anterior sea el next of current y actualice current=current.next . Esto eliminaría el bloque de Nodes con valor 28 que tiene duplicados.
C++
// C++ program to remove all occurrences
// of duplicates from a sorted linked list.
#include <bits/stdc++.h>
using namespace std;
// A linked list node
struct Node
{
int data;
struct Node *next;
};
// Utility function
// to create a new Node
struct Node *newNode(int data)
{
Node *temp = new Node;
temp -> data = data;
temp -> next = NULL;
return temp;
}
// Function to print nodes
// in a given linked list.
void printList(struct Node *node)
{
while (node != NULL)
{
printf("%d ", node -> data);
node = node -> next;
}
}
// Function to remove all occurrences
// of duplicate elements
void removeAllDuplicates(struct Node* &start)
{
// Create a dummy node that acts like
// a fake head of list pointing to the
// original head
Node* dummy = new Node;
// Dummy node points to the original head
dummy -> next = start;
// Node pointing to last node which has
// no duplicate.
Node* prev = dummy;
// Node used to traverse the linked list.
Node* current = start;
while(current != NULL)
{
// Until the current and previous
// values are same, keep updating current
while(current -> next != NULL &&
prev -> next -> data == current -> next -> data)
current = current -> next;
// if current has unique value
// i.e current is not updated,
// Move the prev pointer to
// next node
if (prev -> next == current)
prev = prev -> next;
// When current is updated to the
// last duplicate value of that segment,
// make prev the next of current
else
prev -> next = current -> next;
current = current -> next;
}
// Update original head to the next
// of dummy node
start = dummy -> next;
}
// Driver Code
int main()
{
// 23->28->28->35->49->49->53->53
struct Node* start = newNode(23);
start -> next = newNode(28);
start -> next -> next = newNode(28);
start -> next ->
next -> next = newNode(35);
start -> next ->
next -> next -> next = newNode(49);
start -> next ->
next -> next ->
next -> next = newNode(49);
start -> next ->
next -> next ->
next -> next -> next = newNode(53);
start -> next ->
next -> next ->
next -> next ->
next -> next = newNode(53);
cout << "List before removal " <<
"of duplicates";
printList(start);
removeAllDuplicates(start);
cout << "List after removal " <<
"of duplicates";
printList(start);
return 0;
}
// This code is contributed by NIKHIL JINDAL
Producción:
List before removal of duplicates 23 28 28 35 49 49 53 53 List after removal of duplicates 23 35
Complejidad de tiempo: O (n) ¡
Consulte el artículo completo sobre Eliminar todas las ocurrencias de duplicados de una lista vinculada ordenada para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA