Remove Duplicates from an Unsorted Linked List

Remove Duplicates from an Unsorted Linked List” is one of the foremost problem asked in many technical and algorithmic interviews of product based companies. Here, we are given an unsorted linked list and our task is to remove all duplicate nodes from the given linked list.

Here, we need to take care while removing the duplicate nodes, the order of the nodes must not change.

To do so, we will use two nested loops, outer loop to track current node of the linked list and inner loop to traverse the subsequent linked list and remove every duplicate node with node value as current node by some pointer manipulation.

For example, we need to remove duplicates from the following unsorted list.
LIST:  45 -> 45 -> 46 -> 56 -> 45 -> 68 -> 46
After removing all the duplicates from an unsorted linked list, the list would become:
LIST: 45 -> 46 -> 56 -> 68

The steps required to remove duplicates from an unsorted linked list are as follows:

  1. Initialise the ‘temp’ node with head of the linked list.
  2. Traverse the given linked list with two two loops (nested). The outer loop is used to track the current node of the linked list.
  3. Inner traversing loop will used to traverse the subsequent nodes and compare each node element with ‘temp’ node, if the node value matches, then delete that node.

C++ Program to remove duplicates from an Unsorted Linked List is as follows:

/* C++ Program to remove duplicates from an unsorted linked list */
#include<bits/stdc++.h>
using namespace std;

/* Structure of the node of the linked list */
typedef struct node
{
    int data;
    struct node *next;
}Node;

/* Function to Insert node at the end of the linked list */
void insert_end(Node **head, int ele)
{
    /* Creating a new node */
    Node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
    
    /* check whether the linked list is empty or not */
     
    /* If Linked List is empty, then new node will become head of the linked list */
    if(*head == NULL)     
    {
        *head = new_node;
        return;
    }
    /* If Linked List is not empty, then traverse the complete linked list and point the pointer
    of last node of the linked list to the new node */
    Node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* Function to remove duplicate Nodes from the linked list */
Node *removeDuplicates(Node *head)
{
    Node *curr = head;
    Node *temp = NULL;
    /* Outer Loop is used to track current node */
    while(curr != NULL)
    {
        temp = curr;
        /* Innser loop is used to delete multiple occurrences of the current node */
        while(temp->next != NULL)
        {
            if(temp->next->data == curr->data)
            {
                Node *p = temp->next;
                temp->next = temp->next->next;
                delete p;
            }
            else
                temp = temp->next;
        }
        curr = curr->next;
    }
    return head;
}

/* Function to Print the Linked List  */
void print(Node *head)
{
    Node *temp = head;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}
int main()
{
    Node *head;
    head = NULL;
    /* Inserting Some Nodes in the Linked List */
    insert_end(&head,45);
    insert_end(&head,45);
    insert_end(&head,46);
    insert_end(&head,56);
    insert_end(&head,45);
    insert_end(&head,68);
    insert_end(&head,46);
    cout<<"Linked List Before Removing Duplicate Nodes:\n";
    print(head);
    head = removeDuplicates(head);
    cout<<"Linked List After Removing Duplicate Nodes:\n";
    print(head);
}
OUTPUT:
Linked List Before Removing Duplicate Nodes:
45 45 46 56 45 68 46
Linked List After Removing Duplicate Nodes:
45 46 56 68

Related Posts:

  1. Remove Duplicate Nodes from a Sorted Linked List.
  2. Find Union and Intersection of Two Linked List.
  3. Merge Two Sorted Linked List.
  4. Delete Complete Linked List.
  5. Delete Nth Node of the Linked List.
  6. Delete without head pointer of the Linked List.
  7. Delete All Occurrences of particular node of the Linked List.
  8. Delete Alternate Nodes of the Linked List.
  9. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  10. Insert a New Node at the Sorted Linked List.
  11. Reverse a Linked List.
  12. Reverse a Linked List Using Stack.
  13. Printing Linked List in Reverse Order without actually reversing the Linked List.
  14. Swap Adjacent Elements of the Linked List.
  15. Count All Occurrences of a Particular Node in a Linked List.
  16. Bubble Sort on Linked List.
  17. Detect a Loop in a Linked List.
  18. Find the Length of the Loop present in the Linked List.
  19. Detect and Remove Loop from a Linked List.
  20. Segregate Even and Odd Nodes of the Linked List.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *