Find Common Elements in Three Linked Lists in C++

Suppose we have three linked lists. We have to find all the common elements that are present in these three linked lists. Suppose these lists are [10, 12, 15, 20, 25], [10, 12, 13, 15] and [10, 12, 15, 24, 25, 26], then the common elements in these three lists are 10, 12 and 15.

We will use the hashing technique to solve this problem. To solve this, we have to follow these steps −

• Create an empty hash table, and go through each element in the first table, and insert the elements, and mark the frequency as 1

• Iterate through the second linked list, then if the current frequency is 1 for the element, then make it 2

• Iterate through the third linked list, then if the current frequency is 2 for the element, then make it 3

• Now iterate through the first list again to check the frequency of elements, if there is some element whose frequency is 3, then print that element, and go for next

Example

 Live Demo

#include<iostream>
#include<cmath>
#include<unordered_map>
using namespace std;
class Node {
   public:
      int data;
   Node* next;
};
void addNode(Node** start, int data) {
   Node* newNode = new Node;
   newNode->data = data;
   newNode->next = (*start);
   (*start) = newNode;
}
void findCommonValues(Node* list1, Node* list2, Node* list3) {
   unordered_map<int, int> hash;
   Node* p = list1;
   while (p != NULL) {
      hash[p->data] = 1;
      p = p->next;
   }
   Node* q = list2;
   while (q != NULL) {
      if (hash.find(q->data) != hash.end()) hash[q->data] = 2;
         q = q->next;
   }
   Node* r = list3;
   while (r != NULL) {
      if (hash.find(r->data) != hash.end() && hash[r->data] == 2)
         hash[r->data] = 3;
      r = r->next;
   }
   for (auto x : hash) {
      if (x.second == 3)
         cout << x.first << " ";
   }
}
int main() {
   Node* list1 = NULL;
   addNode(&list1, 10);
   addNode(&list1, 12);
   addNode(&list1, 15);
   addNode(&list1, 20);
   addNode(&list1, 25);
   Node* list2 = NULL;
   addNode(&list2, 10);
   addNode(&list2, 12);
   addNode(&list2, 13);
   addNode(&list2, 15);
   Node* list3 = NULL;
   addNode(&list3, 10);
   addNode(&list3, 12);
   addNode(&list3, 15);
   addNode(&list3, 24);
   addNode(&list3, 25);
   addNode(&list3, 26);
   cout << "Common elements are: ";
   findCommonValues(list1, list2, list3);
}

Output

Common elements are: 10 12 15