educative.io

Union and Intersection of Linked Lists using Maps

Courses
,
#1

A user said the following:

A better solution for the challenge is something like this:

string Intersection(DoublyLinkedList list1, DoublyLinkedList list2) { 

  DoublyLinkedList list3; 
  map MP; 

  for (auto current = list1.getHead(); current != nullptr; current = current->;nextElement) 
    MP[current->data] = 1; 

  for (auto current = list2.getHead(); current != nullptr; current = current->nextElement) { 
    if(MP[current->data]) 
    list3.insertAtTail(current->data); 
    } 

  return list3.elements(); 
}
#2

This is Waleed from Educative. Thank you for reaching out to us!

I have checked your solution and I think you missed the #include <map> at first and then the map MP should be map <int, int> MP . It’ll work fine if you do the same thing for the challenge and also for the solution.

Below is the corrected solution:

string Intersection(DoublyLinkedList list1, DoublyLinkedList list2) { 

  DoublyLinkedList list3; 
  map<int, int> MP; 

  for (auto current = list1.getHead(); current != nullptr; current = current->nextElement){
    MP[current->data] = 1; 
  }

  for (auto current = list2.getHead(); current != nullptr; current = current->nextElement){ 
    if(MP[current->data]) 
    list3.insertAtTail(current->data); 
  } 
  
  return list3.elements(); 
}

This solution is optimized and there is no doubt about it.

Although, some of the users might not know about it till this point as maps are an advanced topic

Best Regards,
Waleed Khalid | Developer Advocate
Educative