Union and Intersection of Two Linked Lists

#include <bits/stdc++.h>
using namespace std;

struct LLNode{
	int data;
	LLNode *next;	
};
void insertAtBeginning(LLNode**head,int dataToBeInserted);
//search function, says whether the element is present in that list or not
int search(LLNode *head, int data) 
{
  LLNode* temp = head;
    while (temp != NULL) {
        if (temp->data == data){
            return 1;
        }
        temp = temp->next;
    }
    return 0;
}
//Finding the union of elements in two linked lists
//By checking whether the element in list2 is present in list1 or not
LLNode* findUnion(LLNode* list1, LLNode* list2)
{
  LLNode* unionLL = NULL;
  LLNode* temp1 = list1;
  LLNode* temp2 = list2;
  //Inserting all the elements in list1 to unionLL list
  while(temp1 != NULL) {
      insertAtBeginning(&unionLL, temp1->data);
      temp1 = temp1->next;
  }
  //If element in list2 is not present in list1
  //then inserting the element to unionLL list
  while(temp2 != NULL) {
      if (!search(list1, temp2->data))
      {
        insertAtBeginning(&unionLL, temp2->data);
      }
      temp2 = temp2->next;
  }
  return unionLL;
}
//Finding the Intersection of elements in two linked lists
//By checking whether the element in list1 is present in list2 or not
LLNode* findIntersection(LLNode* list1, LLNode* list2)
{
  LLNode* intersectionLL = NULL;
  LLNode* temp1 = list1;
  //If element in list1 is present in list2
  //then inserting the element to intersectionLL list
  while(temp1 != NULL) {
      if (search(list2, temp1->data))
      {
        insertAtBeginning(&intersectionLL, temp1->data);
      }
      temp1 = temp1->next;
  }
  return intersectionLL;
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
	LLNode*curr=new LLNode;
	//make a new node with this data and next pointing to NULL
	curr->data=dataToBeInserted;
	curr->next=NULL;

	if(*head==NULL) //if list is empty then set the current formed node as head of list
			*head=curr;
		
	else //make the next of the current node point to the present head and make the current node as the new head
		{
			curr->next=*head;
			*head=curr;
		}
		
		//O(1) constant time
}


void display(LLNode**head)
{
	LLNode*temp=*head;
	while(temp!=NULL) //till the list ends (NULL marks ending of list)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}

int main() 
{    
	LLNode *result = NULL;
  LLNode *unionLL = NULL;
  LLNode *intersectionLL = NULL;

	LLNode *list1 = NULL; //initial list has no elements
	insertAtBeginning(&list1,5);
	insertAtBeginning(&list1,4);
  insertAtBeginning(&list1,8);

  LLNode *list2 = NULL;
  insertAtBeginning(&list2,5);
  insertAtBeginning(&list2,2);
  insertAtBeginning(&list2,8);


	
	cout<<"\nTwo Lists are :-\n";
	display(&list1);
  display(&list2);
	unionLL = findUnion(list1,list2);
	cout<<"Union of two lists"<<endl;
	display(&unionLL);

  intersectionLL = findIntersection(list1,list2);
  cout<<"Intersection of two lists"<<endl;
  display(&intersectionLL);

	return 0;
}