Eliminate duplicates from Linked List using C++ program

Eliminate duplicates from Linked List: In this tutorial, we will learn how to eliminate duplicate elements/nodes from the linked list using a C++ program? By Indrajeet Das Last updated : August 01, 2023

Problem statement

Given a sorted linked list (elements are sorted in ascending order). Eliminate duplicates from the given LL, such that output LL contains only unique elements.

In this question, we are given a sorted linked list with duplicate elements in it. Our task is to remove the duplicate nodes of the linked list. Since the list is sorted, the duplicate elements will be present in consecutive orders, that makes the work a lot easier.

Example

Input format: Linked list elements
(separated by space and terminated by 1)

Sample Input 1 :
1 2 3 3 3 4 4 5 5 5 7 -1

Sample Output 1 :
1 2 3 4 5 7

Lets the list be:
1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 4 -> NULL
The modified list will be:
1 -> 2 -> 3 -> 4 -> NULL

Eliminating duplicates from Linked List

to eliminate duplicates from Linked List, keep the temp pointer pointing to node while(temp -> next != NULL), check if the data of temp is equal to data of temp -> next. If they are equal, then point the temp -> next to temp -> next -> next.

Original LL:  3 ->  3 ->  4 ->  ...
After Change: 3 ->  4 ->  ... //Leaving out the middle 3 ->

This will keep on until we reached the end of the list and return head at the end.

Let's understand these steps with an example -

1) 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 4 -> NULL, temp = 1
2) 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 4 -> NULL, temp = 2
3) 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 4 -> NULL, temp = 3
4) 1 -> 2 -> 3 -> 4 -> 4 -> 4 -> NULL, temp = 4
5) 1 -> 2 -> 3 -> 4 -> 4 -> NULL, temp = 4

Finally,
1 -> 2 -> 3 -> 4 -> NULL

Function / Pseudo Code

Node *removeDuplicate(Node* head){
    //temp pointing to head
    Node *temp = head;
    while(temp -> next != NULL && temp != NULL){
        //Duplicate Found
        if(temp -> data == temp->next->data){      
            //Duplicate Removed
            temp  ->  next = temp  -> next  -> next;    
        }
        else{
            //No Duplicate Present
            temp = temp -> next;
        }
    }
    //Return Head
    return head;
}

C++ program to remove/eliminate duplicates from a linked list

#include <bits/stdc++.h>
using namespace std;

struct Node { // linked list Node
    int data;
    Node* next;
};

Node* newNode(int k)
{ //defining new node
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = k;
    temp->next = NULL;
    return temp;
}

//Used to add new node at the end of the list
Node* addNode(Node* head, int k)
{
    if (head == NULL) {
        head = newNode(k);
    }
    else {
        Node* temp = head;
        Node* node = newNode(k);
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = node;
    }

    return head;
}

// Used to create new linked list and return head
Node* createNewLL()
{
    int cont = 1;
    int data;
    Node* head = NULL;
    while (cont) {
        cout << "Enter the data of the Node" << endl;
        cin >> data;
        head = addNode(head, data);
        cout << "Do you want to continue?(0/1)" << endl;
        cin >> cont;
    }
    return head;
}

//To print the Linked List
void* printLL(Node* head)
{
    while (head != NULL) {
        cout << head->data << "->";
        head = head->next;
    }
    cout << "NULL" << endl;
}

//Function
Node* removeDuplicate(Node* head)
{
    //temp pointing to head
    Node* temp = head;
    while (temp->next != NULL && temp != NULL) {
        //Duplicate Found
        if (temp->data == temp->next->data) {
            //DUplicate Removed
            temp->next = temp->next->next;
        }
        else {
            //No Duplicate Present
            temp = temp->next;
        }
    }
    //Return Head
    return head;
}

// Main code
int main()
{
    Node* head = createNewLL();
    
    cout << "The linked list is" << endl;
    printLL(head);

    head = removeDuplicate(head);
    cout << "The new Linked List is" << endl;
    printLL(head);

    return 0;
}

Output

Enter the data of the Node
1
Do you want to continue?(0/1)
1
Enter the data of the Node
1
Do you want to continue?(0/1)
1
Enter the data of the Node
2
Do you want to continue?(0/1)
1
Enter the data of the Node
2
Do you want to continue?(0/1)
1
Enter the data of the Node
3
Do you want to continue?(0/1)
1
Enter the data of the Node
4
Do you want to continue?(0/1)
1
Enter the data of the Node
5
Do you want to continue?(0/1)
1
Enter the data of the Node
5
Do you want to continue?(0/1)
1
Enter the data of the Node
5
Do you want to continue?(0/1)
0
The linked list is
1->1->2->2->3->4->5->5->5->NULL
The new Linked List is
1->2->3->4->5->NULL