Linked List: Remove duplicates from an unsorted linked list

Problem Statement:

You are given an un-sorted Linked List.
You need to remove the duplicate nodes.

Example

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

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

Solution

In this solution, we will use 2 loops.

For every element in outer loop, inner loop will check all the elements in the LL.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

#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;
    }
}

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");
}


void remove_duplicates(struct Node *start)
{
    struct Node *ptr1;
    struct Node *ptr2;
    struct Node *dup;

    ptr1 = start;
 
    while (ptr1 != NULL && ptr1->next != NULL)
    {
        ptr2 = ptr1;
 
        while (ptr2->next != NULL)
        {
            if (ptr1->data == ptr2->next->data)
            {
                dup = ptr2->next;
                ptr2->next = ptr2->next->next;
                delete(dup);
            }
            else 
                ptr2 = ptr2->next;
        }
        ptr1 = ptr1->next;
    }
}

   int main()
{
    struct Node *list_1 = NULL; 
    struct Node *result = NULL; 
    int k = 2;

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

    printf("Original List\n");
    display_list(&list_1);

    remove_duplicates(list_1);
    printf("The result list is\n");
    
    display_list(&list_1);

    return 0;
}

Output:

Original List
1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 4 -> 5
The result list is
1 -> 2 -> 3 -> 4 -> 5