RUN


Given: A link list(LL) that is not sorted and contains duplicate nodes. We have to remove these duplicate nodes.

Example:

Given LL: 13, 16, 13, 21, 25, 13, 30, 26, 13.

Output: 13, 16, 21, 25, 30, 26.

# Brute Force Approach

In this, we compare each element with the rest of the elements.

Code:

// Program to remove duplicates in an unsorted  LL
#include <bits/stdc++.h>
using namespace std;

// LL node

struct Node

{

	int info;

	struct Node * next;

};

// function to create a new Node 

struct Node* createNode(int info)

{

	Node *temp = new Node;

	temp->info = info;

	temp->next = NULL;

	return temp;

}

// Function removes duplicates from LL 

void revdup(struct Node *first)

{

	struct Node *ptr1, *ptr2, *dupli;

	ptr1 = first;

	// Picking elements one at a time 

	while (ptr1 != NULL && ptr1->next != NULL)

	{

		ptr2 = ptr1;

		// Comparing the picked element with rest elements 

		while (ptr2->next != NULL)

		{

			// If duplicate then delete it 

			if (ptr1->info == ptr2->next->info)

			{

				dupli = ptr2->next;

				ptr2->next = ptr2->next->next;

				delete(dupli);
			}
			else

				ptr2 = ptr2->next;
		}

		ptr1 = ptr1->next;
	}
}

// Function to print nodes of given LL

void printLL(struct Node *node)

{

	while (node != NULL)

	{

		printf("%d ", node->info);

		node = node->next;
	}
}

// Driver code

int main()

{

	/*The constructed linked list is: 

	3, 4, 5, 1, 2, 4, 4*/

	struct Node *first = createNode(3);

	first->next = createNode(4);

	first->next->next = createNode(5);

	first->next->next->next = createNode(1);

	first->next->next->next->next = createNode(2);

	first->next->next->next->next->next = createNode(4);

	first->next->next->next->next->next->next = createNode(4);

	cout << "before removing the duplicate elements : ";

	printLL(first);

	revdup(first);

	cout << "after removing the duplicate elements : ";

	printLL(first);

	return 0;

}

Time Complexity: O(n2)

# Optimized Approach

We go through the LL from first to last. For each new element, we check if it is in the hash table. If it is there then we will remove it else we put it in the hash table.

Code:

#include <iostream>
#include <unordered_set>
using namespace std;

// LL node

struct Node

{

	int info;

	Node * next;

};

// function to print given LL

void printLL(Node *first)

{

	Node *ptr = first;

	while (ptr)

	{

		cout << ptr->info;

		ptr = ptr->next;

		cout << ", ";
	}

	cout << "NULL";

}

// function to insert a new node in the beginning of LL

void push(Node **ref, int info)

{

	Node *createNode = new Node();

	createNode->info = info;

	createNode->next = *ref;

	*ref = createNode;

}

// Function to remove duplicates from unsorted list

void revdup(Node *first)

{

	Node *previous = nullptr;

	Node *present = first;

	// take an empty uno_set to store LL nodes

	unordered_set<int> uno_set;

	// until LL is empty

	while (present != nullptr)

	{

		// if present node is repeated, delete it

		if (uno_set.find(present->info) != uno_set.end())

		{

			previous->next = present->next;

			delete present;
		}
		else

		{

			// insert present node into the uno_set and go to next node

			uno_set.insert(present->info);

			previous = present;
		}

		present = previous->next;
	}
}

// driver code

int main()

{

	// input the LL(input)

	int input[] = { 3, 4, 5, 1, 2, 4, 4, 5, 6, 11, 18 };

	int size = sizeof(input) / sizeof(input[0]);

	// pointing first node of LL

	Node *first = nullptr;

	// build LL

	for (int i = size - 1; i >= 0; i--)

		push(&first, input[i]);

	revdup(first);

	printLL(first);

	return 0;

}

Time Complexity: O(n) on average (assuming that hash table access time is O(1) on average).

Report Error/ Suggestion

Related Posts:




CopyRight © 2020

CopyRight © 2020