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