Escriba una función que tome una lista ordenada en orden no decreciente y elimine cualquier Node duplicado de la lista. La lista solo debe recorrerse una vez.
Por ejemplo, si la lista vinculada es 11->11->11->21->43->43->60, removeDuplicates() debería convertir la lista a 11->21->43->60.
Algoritmo:
recorrer la lista desde el Node principal (o inicial). Mientras atraviesa, compare cada Node con su siguiente Node. Si los datos del siguiente Node son los mismos que los del Node actual, elimine el siguiente Node. Antes de eliminar un Node, debemos almacenar el siguiente puntero del Node
Implementación:
las funciones que no sean removeDuplicates() son solo para crear una lista vinculada y probar removeDuplicates().
C
// C Program to remove duplicates
// from a sorted linked list
#include<stdio.h>
#include<stdlib.h>
// Link list node
struct Node
{
int data;
struct Node* next;
};
// The function removes duplicates
// from a sorted list
void removeDuplicates(struct Node* head)
{
// Pointer to traverse the linked list
struct Node* current = head;
// Pointer to store the next pointer
// of a node to be deleted
struct Node* next_next;
// Do nothing if the list is empty
if (current == NULL)
return;
// Traverse the list till last node
while (current->next != NULL)
{
// Compare current node with next node
if (current->data == current->next->data)
{
// The sequence of steps is important
next_next = current->next->next;
free(current->next);
current->next = next_next;
}
// This is tricky: only advance
// if no deletion
else
{
current = current->next;
}
}
}
// UTILITY FUNCTIONS
// Function to insert a node at the
// beginning of the linked list
void push(struct Node** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
// Put in the data
new_node->data = new_data;
// Link the old list off the new node
new_node->next = (*head_ref);
// Move the head to point to the
// new node
(*head_ref) = new_node;
}
// Function to print nodes in a given
// linked list
void printList(struct Node *node)
{
while (node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
// Driver code
int main()
{
// Start with the empty list
struct Node* head = NULL;
/* Let us create a sorted linked list
to test the functions. Created
linked list will be
11->11->11->13->13->20 */
push(&head, 20);
push(&head, 13);
push(&head, 13);
push(&head, 11);
push(&head, 11);
push(&head, 11);
printf(
"Linked list before duplicate removal ");
printList(head);
// Remove duplicates from linked list
removeDuplicates(head);
printf(
"Linked list after duplicate removal ");
printList(head);
return 0;
}
Producción:
Linked list before duplicate removal 11 11 11 13 13 20 Linked list after duplicate removal 11 13 20
Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada dada.
Enfoque recursivo:
C
// C recursive Program to remove duplicates
// from a sorted linked list
#include<stdio.h>
#include<stdlib.h>
// Link list node
struct Node
{
int data;
struct Node* next;
};
// UTILITY FUNCTIONS
// Function to insert a node at
// the beginning of the linked list
void push(struct Node** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
// Put in the data
new_node->data = new_data;
// Link the old list off the
// new node
new_node->next = (*head_ref);
// Move the head to point to the
// new node
(*head_ref) = new_node;
}
// Function to print nodes in a
// given linked list
void printList(struct Node *node)
{
while (node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
Node* deleteDuplicates(Node* head)
{
if (head == nullptr)
return nullptr;
if (head->next == nullptr)
return head;
if (head->data == head->next->data)
{
Node *tmp;
// If find next element duplicate,
// preserve the next pointer to be
// deleted, skip it, and then delete
// the stored one. Return head
tmp = head->next;
head->next = head->next->next;
free(tmp);
return deleteDuplicates(head);
}
else
{
// if doesn't find next element duplicate, leave head
// and check from next element
head->next = deleteDuplicates(head->next);
return head;
}
}
// Driver code
int main()
{
// Start with the empty list
struct Node* head = NULL;
/* Let us create a sorted linked list
to test the functions. Created
linked list will be 11->11->11->13->13->20 */
push(&head, 20);
push(&head, 13);
push(&head, 13);
push(&head, 11);
push(&head, 11);
push(&head, 11);
printf(
"Linked list before duplicate removal ");
printList(head);
// Remove duplicates from linked list
head = deleteDuplicates(head);
printf(
"Linked list after duplicate removal ");
printList(head);
return 0;
}
// This code is contributed by Yogesh shukla
Producción:
Linked list before duplicate removal 11 11 11 13 13 20 Linked list after duplicate removal 11 13 20
Complejidad de tiempo: O(n), donde n es el número de Nodes en la lista enlazada dada.
Espacio auxiliar: O(n), debido a la pila recursiva donde n es el número de Nodes en la lista enlazada dada.
Consulte el artículo completo sobre Eliminar duplicados de una lista ordenada 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