Learn basic concept of c , c++ and python programming in regularcodes.com

Intersection of two linked lists

If two different linked list are contain same node value then it is called intersection of two linked list. note that if same node value find two or more then time then include once.

Assume that given two linked list (L1 and L2) and find intersection of two linked lists.

Given L1 Linked list.

View insertion process.

Try it yourself

Given L2 Linked list.

View insertion process.

Try it yourself

Result:

Overview of solution.

c program to find Intersection of given two linked list.

  
/*Help of this program we are learning how to find Intersection of given two linked list.
Time complexity O(n^2). Iterative solution.*/

/*include header file*/
#include<stdio.h>
#include<stdlib.h>


/*Structure of linked list*/
struct Node{
  int data;// linked list data 
  struct Node*next;// pointer field
  
};

/* Function declaration section here */
struct Node*create_node(int);
void insert_data(struct Node**,int);
void show_data(struct Node*);
void remove_node(struct Node**);
void intersection(struct Node*,struct Node*,struct Node**);
void ints_data(struct Node**,int);

/*Help of this function create new linked list node.*/
struct Node*create_node(int value){

  struct Node *new_node=(struct Node*)malloc(sizeof(struct Node));
  /* check new create memory are allocate or not. */
  if(new_node){  
    new_node->data=value;
    new_node->next=NULL;
    /*return the address of new_node*/
    return new_node; 
  }
  else{ 
    /*Memory Overflow*/
    return NULL;
  }

}

/* 
And there are inserted this element on end position of given linked list*/
void insert_data(struct Node**root,int value){
  if(*root==NULL){
    /*Empty linked list.*/
    *root=create_node(value);
  }
  else{

     /*When linked list are empty. Insert first node*/

    /*linked list first node address assign on temp pointer*/
     struct Node*temp=*root;

      /*This will loop find last node of exist linked list*/
      while(temp!=NULL && temp->next!=NULL){
        /*move temp pointer on next memory block*/
        temp=temp->next;  
      }
      
      /*Assign this newly created node on end of list*/
      temp->next=create_node(value);
  }

}


/* Help of this function showing all element of single linked list */
void show_data(struct Node*temp){
  if(temp==NULL){
    /*linked list are empty*/
    printf("Empty linked List\n");
  }
  else
  {
    while(temp)
    {
      /*print linked list data*/
      printf("%d  ",temp->data);

      /*move next memory block*/
      temp=temp->next;
    }
    
  }
}

/*Help of this function removing all linked list element.*/
void remove_node(struct Node**root){
  
  if(*root!=NULL){
    struct Node*temp=*root;
    while(temp){
      /*Moving root pointer to on next memory block.*/
      *root=temp->next;
      /*Before removing that linked node assign
       next pointer value are null.*/
      temp->next=NULL;
      
      /*Free linked list node element*/
      free(temp);
      
      temp=*root;
    }
    
  }
  else{
    /* When linked list is empty */
    printf("\n linked list is empty \n");
  } 
}


void  ints_data(struct Node**l3,int value){

  
  if(*l3==NULL){
    /*linked list are empty*/
    *l3=create_node(value);
  }
  int status=1;
  struct Node*helper=*l3;

  while(helper!=NULL && helper->next !=NULL){
    if(helper->data==value){
      status=0;
      break;
    }
    /*move next memory block*/
    helper=helper->next;
  }

  /*if inserted value are not find in L3 linked list.*/
  if(status && (*l3)->data!=value){
    helper->next=create_node(value);   
  }
 

}


/*Check intersection of L1 and L2 linked list.*/
void intersection(struct Node*l1,struct Node*l2,struct Node**l3){

    struct Node*temp=l2;
    
    while(l1!=NULL){
         
         temp=l2;   
        while(temp!=NULL){

          /*check same node data*/
          if(temp->data==l1->data){
            /*find intersection*/
            ints_data(l3,temp->data);
            break;
          }
          /*move next memory block*/
          temp=temp->next;
        }
        /*move next memory block*/
        l1=l1->next;
    }


}


int main(){
  /* start program execution are here */

  struct Node*l1=NULL,*l2=NULL,*l3=NULL;
  
  /*L1: linked list*/
  /*Following data are inserted */  
  insert_data(&l1,1);
  insert_data(&l1,4);
  insert_data(&l1,9);
  insert_data(&l1,3);
  insert_data(&l1,8);
  insert_data(&l1,4);

  /*L2: linked list*/
  /*Following data are inserted */
  insert_data(&l2,1);
  insert_data(&l2,1);
  insert_data(&l2,8);
  insert_data(&l2,9);
  insert_data(&l2,5);
  insert_data(&l2,4);
  insert_data(&l2,3);
  insert_data(&l2,2);




  printf("\n Linked list L1 :");
   
  /*View L1 linked list data*/
  show_data(l1);

  printf("\n Linked list L2 :");
   
 /*View L2 linked list data*/
  show_data(l2);

  intersection(l1,l2,&l3);

  printf("\n Linked list L3 :");
   
  /*View L3 linked list data*/
   show_data(l3);

 /*Removing linked list node*/
  remove_node(&l1);
  remove_node(&l2);
  remove_node(&l3);
  /*end execution*/
}