Remove Duplicates from a Sorted Linked List

Remove Duplicates from a Sorted Linked List” is one of the foremost problem of linked list data structure asked in many technical and algorithmic interviews of product-based company. 

Here, we are given a sorted linked list and our task is to remove duplicates from a sorted linked list.

For example, we need to remove all the duplicate nodes from the following list.
List:   45 -> 45 -> 46 -> 56 -> 67 -> 68 -> 68
After deleting duplicate nodes from a linked list, the linked list will become:
          List: 45 -> 46 -> 56 -> 67 -> 68

The steps required to remove duplicates from a sorted linked list is as follows:

  1. Traverse the complete linked list from head node to last node.
  2. While traversing, if the data of current node is equal to data of next node, point the pointer of current node to next of next and delete the next node of current node.

The time complexity of given solution will O(n), where ‘n’ represents the number of nodes present in the linked list. The time complexity is linear because we are traversing the given linked list only one time.

C++ Program to remove duplicates from a Sorted Linked List is as follows:

/* C++ Program to remove duplicates from a sorted 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 sorted linked list */
Node *removeDuplicates(Node *head)
{
    /*
    Traverse the complete linked list.While traversing, if the data of 
    current node is equal to data of next node, point the pointer of 
    current node to next of next and delete the next node of current node.
    */
    Node *temp = head;
    while(temp->next!=NULL)
    {
        if(temp->data == temp->next->data)
        {
            Node *p = temp->next;
            temp-> next = p->next;
            delete p;
        }
        else
        {
            temp = temp -> 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 in sorted manner */
    insert_end(&head,45);
    insert_end(&head,45);
    insert_end(&head,46);
    insert_end(&head,56);
    insert_end(&head,67);
    insert_end(&head,68);
    insert_end(&head,68);
    cout<<"Linked List Before Removing Duplicates:\n";
    print(head);
    cout<<"\nLinked List After Removing Duplicates:\n";
    head = removeDuplicates(head);
    print(head);
}
OUTPUT:
Linked List Before Removing Duplicates:
45 45 46 56 67 68 68
Linked List After Removing Duplicates:
45 46 56 67 68

Related Posts:

  1. Remove Duplicate Nodes from an Unsorted Linked List.
  2. Delete Complete Linked List.
  3. Delete Nth Node of the Linked List.
  4. Delete without head pointer of the Linked List.
  5. Delete All Occurrences of particular node of the Linked List.
  6. Delete Alternate Nodes of the Linked List.
  7. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  8. Find Union and Intersection of Two Linked List.
  9. Merge Two Sorted 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...