Union and Intersection of Two Linked Lists

Given two linked lists, find the union and intersection of the elements in two linked lists.

Example

Two Lists are :-
list1 = 8 ->4 ->5
list2 = 8 ->2 ->5

Union of two lists
2 ->5 ->4 ->8

Intersection of two lists
5 ->8

NOTE : In both union and intersection lists, the elements need not be in order.

Time Complexity : O(mn),

where m is the number of elements in list1 and n is the number of elements in list2

Algorithm

Union

1. Traverse list1 and insert all the elements in list1 to output list

2. Traverse list2 and check whether the element is present in list1 or not. If not present insert the element to output list.

Intersection :

1. Traverse list1 and check whether the element is present in list2 or not. If present insert the element to output list.

C++ Program

#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;
}

 

Translate ยป