C++ Program For Removing All Occurrences Of Duplicates From A Sorted Linked List - Coding

Given a sorted linked list, delete all nodes that have duplicate numbers (all occurrences), leaving only numbers that appear once in the original list.
Examples:

Input: 23->28->28->35->49->49->53->53
Output: 23->35

Input: 11->11->11->11->75->75
Output: empty List

Note that this is different from Remove Duplicates From Linked List

The idea is to maintain a pointer (prev) to the node which just previous to the block of nodes we are checking for duplicates. In the first example, the pointer prev would point to 23 while we check for duplicates for node 28. Once we reach the last duplicate node with value 28 (name it current pointer), we can make the next field of prev node to be the next of current and update current=current.next. This would delete the block of nodes with value 28 which has duplicates.

C++

// C++ program to remove all occurrences 
// of duplicates from a sorted linked list.
#include <bits/stdc++.h>
using namespace std;
 
// A linked list node
struct Node
{
    int data;
    struct Node *next;
};
 
// Utility function 
// to create a new Node
struct Node *newNode(int data)
{
    Node *temp = new Node;
    temp -> data = data;
    temp -> next = NULL;
    return temp;
}
 
// Function to print nodes 
// in a given linked list.
void printList(struct Node *node)
{
    while (node != NULL)
    {
        printf("%d ", node -> data);
        node = node -> next;
    }
}
 
// Function to remove all occurrences
// of duplicate elements
void removeAllDuplicates(struct Node* &start)
{
    // Create a dummy node that acts like 
    // a fake head of list pointing to the 
    // original head
    Node* dummy = new Node;
 
    // Dummy node points to the original head
    dummy -> next = start;
     
    // Node pointing to last node which has 
    // no duplicate.
    Node* prev = dummy;
     
    // Node used to traverse the linked list.
    Node* current = start;
 
    while(current != NULL)
    {
        // Until the current and previous 
        // values are same, keep updating current
        while(current -> next != NULL &&
              prev -> next -> data == current -> next -> data)
            current = current -> next;
 
        // if current has unique value 
        // i.e current is not updated, 
        // Move the prev pointer to 
        // next node
        if (prev -> next == current)
            prev = prev -> next;
 
        // When current is updated to the 
        // last duplicate value of that segment, 
        // make prev the next of current
        else
            prev -> next = current -> next;
 
        current = current -> next;
    }
 
    // Update original head to the next 
    // of dummy node 
    start = dummy -> next;
}
 
// Driver Code
int main() 
{
    // 23->28->28->35->49->49->53->53
    struct Node* start = newNode(23);
    start -> next = newNode(28);
    start -> next -> next = newNode(28);
    start -> next -> 
             next -> next = newNode(35);
    start -> next -> 
    next -> next -> next = newNode(49);
    start -> next -> 
    next -> next -> 
    next -> next = newNode(49);
    start -> next -> 
    next -> next -> 
    next -> next -> next = newNode(53);
    start -> next -> 
    next -> next -> 
    next -> next -> 
    next -> next = newNode(53);
    cout << "List before removal " <<
            "of duplicates";
    printList(start);
     
    removeAllDuplicates(start);
     
    cout << "List after removal " << 
            "of duplicates";
    printList(start);
    return 0;
}
// This code is contributed by NIKHIL JINDAL

Output:

List before removal of duplicates
23 28 28 35 49 49 53 53 
List after removal of duplicates
23 35

Time Complexity: O(n)

Auxiliary Space: O(1) because using constant variables

Please refer complete article on Remove all occurrences of duplicates from a sorted Linked List for more details!

Reffered: https://www.geeksforgeeks.org

C++ Programs

Related
Calling a non-member function inside a class in C++
C++ Program For Pairwise Swapping Elements Of A Given Linked List By Changing Links
C++ program to convert/normalize the given time into standard form
C++ program to implement Full Adder
Flying Bird using Computer graphics in C/C++

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11