Perform Union and Intersection of two linked lists in C++

In this post, we will learn about finding intersection and union from two linked lists in C++. The union of two arrays is the set of all elements that are either in A or in B.  Intersections are the elements that are common in both the lists.

C++ Program to Perform Union and Intersection of two linked lists

#include<iostream>
using namespace std;
class Node
{
    public:
    int data;
    Node*next;
};

In the above code, we have declared a Node class which is the body of a class. This is the structure of the Node that will be created every time you call Node.

CLASS: LinkedList

class LinkedList
{
    private:
    Node *head;
    public:
    LinkedList()
    {
        head=NULL;
    }
    //LinkedList(int A[],int n);
/*In this method it takes two argumnet, firts is reference to a head and a data of int type
And by pushing every element at first position creates a Linked list.
*/

    void push(Node** head,int data)
    {
        Node *new_node=new Node;
        new_node->data=data;
        new_node->next=*head;
        *head=new_node;
    }
/*This Method takes two reference pointers and thus provides intersection between them by pushing 
all the similar elements from both lists. Thus returns reference to a list of result.
*/
    Node* getIntersection(Node *head1,Node *head2)
    {
        Node *n1=head1;
        Node *result=NULL;
        while(n1!=NULL)
        {
            if(ispresent(head2,n1->data))
                push(&result,n1->data);
            n1=n1->next;
        }
    

        return result;
    
    }
/*This Method takes two reference pointers and thus provides intersection between them by first pushing all the  elements from first list to result and them check wheather the element from second list, is present in the result list. If not then push action is performed on that element. Thus returns reference to a list of result.
*/
    Node* getUnion(Node* head1,Node *head2)
    {
        Node* result=NULL;
        Node*n1=head1,*n2=head2;
        while(n1!=NULL)
       {
          
           push(&result,n1->data);
           n1=n1->next;
       }
        while(n2!=NULL)
       {
           if(!ispresent(result,n2->data))
               push(&result,n2->data);
           n2=n2->next;
       }
        
        return result;
    }
//Checking wheather the element is present in the list or not.
    bool ispresent(Node *head,int data)
    {
        while(head!=NULL)
        {
            if(head->data==data)
            return 1;
            head=head->next;
        }
        return 0;
    }
//This function takes the reference of head and print a whole Linked list.
    void PrintList(Node *head)
    {
        while(head!=NULL)
        {
            cout<<head->data<<" ";
            head=head->next;
        }
    }
};

int main()
{
    LinkedList ll;
     Node* head1 = NULL;
     Node* head2 = NULL;
     Node* intersection = NULL;
     Node* Union = NULL;

//Pushing element one by one to list with head pointe head1.
    /*create a linked lits 41->15->43->80 */
    ll.push (&head1, 80);
    ll.push (&head1, 43);
    ll.push (&head1, 15);
    ll.push (&head1, 41);
  
    /*create a linked lits 89->41->43->40 */
//Pushing element one by one to list with head pointe head2.
    ll.push (&head2, 40);
    ll.push (&head2, 43);
    ll.push (&head2, 41);
    ll.push (&head2, 89);
    ll.PrintList(head1);
    cout<<endl;
    ll.PrintList(head2);
    cout<<endl;
   //It stores the address to the result pointer which is holding result of union
    Union=ll.getUnion(head1, head2);
    //It stores the address to the result pointer which is holding result of Intersection
    intersection=ll.getIntersection(head1, head2);
    cout<<"Union:";
    ll.PrintList(Union);
    cout<<endl;
    cout<<"Intersection:";
    ll.PrintList(intersection);
    cout<<endl;
    return 0;
}

OUTPUT:

41 15 43 80 

89 41 43 40 

Union:40 89 80 43 15 41 

Intersection:43 41 

Time Complexity of this program is O(M+N) as it traverses through both the lists.

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *