I want an alternative approach to solve the given problem for large number of nodes in a linked list within time Constraints:
1 <= T <= 100
1 <= N <= 10 ^ 4
1 <= data <= 10 ^ 5
I am using map data structure from STL. If node is not visited ( means it’s node->data
stored in map is not equal to true), I update the map and make it node->data
equal to true. If it’s present I remove that node.
This works fine for less number of nodes. But If there are more nodes it exceeds the time limit.
Suggest me alternative approach.
Node *removeDuplicates(Node* &head)
{
// if only has one node
if (head == nullptr || head->next == nullptr)
{
return head;
}
Node * curr = head;
Node * prev = nullptr;
map<int , bool> myMap;
while(curr != nullptr){
if(myMap[curr->data] == true){
Node * nodeToDelete = curr;
curr = curr->next;
prev->next = curr;
delete(nodeToDelete);
}
else{
myMap[curr->data] = true;
prev = curr;
curr = curr->next;
}
}
return head;
}