Remove Duplicates from Sorted List solution in CPP

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

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

Example 2:

Input: 1->1->1->2->3
Output: 2->3

Solution:

For the solution we take 2 nodes a “dummy” node and a “current” node.

Use “dummy” node, incase if head is needed to be deleted.

“current” node is used to iterate through out the list.

So in the solution, first we check if the current node value and next node value are same. Then save the value.
Then we use another while loop, to iterate till we get a unique value.

The important point here is to delete the duplicate node to avoid memory leak.

Solution in C++

/*
* File     : remove_duplicates_from_sorted_list_II.cpp
*/

#include<iostream>
#include<vector>

using namespace std;

struct Node 
{
    int data;
    struct Node* next;
};

void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

Node* deleteDuplicates(Node* head) 
{
    Node* dummy = new Node;
    dummy->next = head;
    Node* cur = dummy;
    int duplicate;
    while (cur->next && cur->next->next) 
    {
        if (cur->next->data == cur->next->next->data) 
        {
            // save the duplicate element
            duplicate = cur->next->data;

            //Loop till you get next unique element.
            while (cur->next && cur->next->data == duplicate) 
            {
                // Delete the node to avoid memory leak.
                Node *temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }
        }
        else 
        {
            cur = cur->next;
        }
    }
    return dummy->next;
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}


int main()
{
    struct Node *list= NULL;
    struct Node *result= NULL;


    insert_at_begenning(&list,5);
    insert_at_begenning(&list,4);
    insert_at_begenning(&list,4);
    insert_at_begenning(&list,3);
    insert_at_begenning(&list,3);
    insert_at_begenning(&list,2);
    insert_at_begenning(&list,1);


    cout<<"Input List is:\n";
    display_list(&list);

    result = deleteDuplicates(list);

    cout<<"\nOutput List is:\n";
    display_list(&result);

    cout<<endl;

return 0;

}

Output:

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

Output List is:
1 -> 2 -> 5