Remove duplicates from a linked list (sorted and unsorted linked list) | faceprep

Program to remove duplicates from a linked list (sorted and unsorted linked list) is discussed here. Given a linked list, print the linked list remove duplicate elements from it.

Remove duplicates from a sorted linked list

Input: 1 -> 2 -> 2 -> 3 -> 4 -> 5 -> 5

Output: 1 -> 2 -> 3 -> 4 -> 5

Remove duplicates from an unsorted linked list

Input: 7 -> 7 -> 19 -> 11 -> 9 -> 11

Output: 7 -> 19 -> 11 -> 9

Algorithm to remove duplicates from a  linked list (sorted)

  • Input the number of elements of the linked list.
  • Input the elements of the linked list in sorted order.
  • Traverse from the head of the sorted linked list.
  • While traversing, compare the currrent node with the next node.
  • If data of the next node is the same as the current node then delete the next node. 

Program to remove duplicates from a sorted linked list is given below.

/* C Program to remove duplicates from a linked list */
#include<stdio.h>
#include<stdlib.h>

/* Structure for a node */
struct node
{
int data;
struct node* next;
};

/* Function to insert a node */
void insert_elements(struct node** head, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node -> data = new_data;
new_node -> next = (*head);
(*head) = new_node;
}


/* Function to print nodes */
void display_list(struct node *node)
{
while (node!=NULL)
{
printf(“%d “, node->data);
node = node -> next;
}
}

/* Function to remove duplicates from a sorted list */
void remove_duplicate_elements(struct node* head)
{
struct node* current = head;

struct node* next_next;

if (current == NULL)
return;

while (current -> next != NULL)
{
/* Compare current node with its next */
if (current -> data == current -> next -> data)
{
next_next = current -> next -> next;
free(current -> next);
current -> next = next_next;
}
else
{
current = current -> next;
}
}
}


int main()
{
struct node* head = NULL;
int n;
printf(“\nEnter the total number of elements : “);
scanf(“%d”, &n);
printf(“\nEnter the sorted linked list : “);
int i;
for(i = 0; i < n; i++)
{
int data;
scanf(“%d”, &data);
insert_elements(&head, data);
}

printf(“\nLinked list before removing duplicates : “);
display_list(head);
printf(“\n”);

remove_duplicate_elements(head);

printf(“\nLinked list after removing duplicates : “);
display_list(head);
printf(“\n”);


return 0;
}

/* C++ Program to remove duplicates from a linked list */
#include<iostream>
#include<stdlib.h>
using namespace std;

/* Structure for a node */
struct node
{
int data;
struct node* next;
};

/* Function to insert a node */
void insert_elements(struct node** head, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node -> data = new_data;
new_node -> next = (*head);
(*head) = new_node;
}


/* Function to print nodes */
void display_list(struct node *node)
{
while (node!=NULL)
{
cout << node -> data << ” “;
node = node -> next;
}
}

/* Function to remove duplicates from a sorted list */
void remove_duplicate_elements(struct node* head)
{
struct node* current = head;

struct node* next_next;

if (current == NULL)
return;

while (current -> next != NULL)
{
/* Compare current node with its next */
if (current -> data == current -> next -> data)
{
next_next = current -> next -> next;
free(current -> next);
current -> next = next_next;
}
else
{
current = current -> next;
}
}
}


int main()
{
struct node* head = NULL;
int n;
cout << “\nEnter the total number of elements : “;
cin >> n;
cout << “\nEnter the sorted linked list : “;
int i;
for(i = 0; i < n; i++)
{
int data;
cin >> data;
insert_elements(&head, data);
}

cout << “\nLinked list before removing duplicates : “;
display_list(head);
cout << endl;

remove_duplicate_elements(head);

cout << “\nLinked list after removing duplicates : “;
display_list(head);
cout << endl;


return 0;
}

Output:

remove duplicates from a linked list - sorted

Algorithm to remove duplicates from a linked list (unsorted)

  • Input the number of elements of the linked list.
  • Input the elements of the linked list.
  • Use two loops, one for traversing the linked list and the other loop to check if the current element is already present in the list.

Program to remove duplicate elements from an unsorted linked list is given below.

/* C program to remove duplicates from a linked list */
#include<stdio.h>
#include<stdlib.h>

/* Structure for a node */
struct node
{
int data;
struct node* next;
};

/* Function to insert a node */
void insert_elements(struct node** head, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node -> data = new_data;
new_node -> next = (*head);
(*head) = new_node;
}


/* Function to print nodes */
void display_list(struct node *node)
{
while (node!=NULL)
{
printf(“%d “, node -> data);
node = node -> next;
}
}

/* Function to remove duplicates from a sorted list */
void remove_duplicate_elements(struct node *temp)
{
struct node *ptr1, *ptr2, *duplicate;
ptr1 = temp;

while (ptr1 != NULL && ptr1->next != NULL)
{
ptr2 = ptr1;

/* Compare the current element with rest of the elements */
while (ptr2->next != NULL)
{
if (ptr1->data == ptr2->next->data)
{
duplicate = ptr2->next;
ptr2->next = ptr2->next->next;
delete(duplicate);
}
else
ptr2 = ptr2->next;
}
ptr1 = ptr1->next;
}
}


int main()
{
struct node* head = NULL;
int n;
printf(“\nEnter the total number of elements : “);
scanf(“%d”, &n);
printf(“\nEnter the unsorted linked list : “);
int i;
for(i = 0; i < n; i++)
{
int data;
scanf(“%d”, &data);
insert_elements(&head, data);
}

printf(“\nLinked list before removing duplicates : “);
display_list(head);
printf(“\n”);

remove_duplicate_elements(head);

printf(“\nLinked list after removing duplicates : “);
display_list(head);
printf(“\n”);


return 0;
}

/* C++ Program to remove duplicates from a linked list */
#include<iostream>
#include<stdlib.h>
using namespace std;

/* Structure for a node */
struct node
{
int data;
struct node* next;
};

/* Function to insert a node */
void insert_elements(struct node** head, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node -> data = new_data;
new_node -> next = (*head);
(*head) = new_node;
}


/* Function to print nodes */
void display_list(struct node *node)
{
while (node!=NULL)
{
cout << node -> data << ” “;
node = node -> next;
}
}

/* Function to remove duplicates from a sorted list */
void remove_duplicate_elements(struct node *temp)
{
struct node *ptr1, *ptr2, *duplicate;
ptr1 = temp;

while (ptr1 != NULL && ptr1->next != NULL)
{
ptr2 = ptr1;

/* Compare the current element with rest of the elements */
while (ptr2->next != NULL)
{
if (ptr1->data == ptr2->next->data)
{
duplicate = ptr2->next;
ptr2->next = ptr2->next->next;
delete(duplicate);
}
else
ptr2 = ptr2->next;
}
ptr1 = ptr1->next;
}
}


int main()
{
struct node* head = NULL;
int n;
cout << “\nEnter the total number of elements : “;
cin >> n;
cout << “\nEnter the unsorted linked list : “;
int i;
for(i = 0; i < n; i++)
{
int data;
cin >> data;
insert_elements(&head, data);
}

cout << “\nLinked list before removing duplicates : “;
display_list(head);
cout << endl;

remove_duplicate_elements(head);

cout << “\nLinked list after removing duplicates : “;
display_list(head);
cout << endl;


return 0;
}