// C program to get intersection point of two linked list  
#include<stdio.h> 
#include<stdlib.h> 
  
/* Link list node */
struct Node 
{ 
  int data; 
  struct Node* next; 
}; 
  
/* Function to get the counts of node in a linked list */
int getCount(struct Node* head); 
  
/* function to get the intersection point of two linked 
   lists head1 and head2 where head1 has d more nodes than 
   head2 */
int _getIntesectionNode(int d, struct Node* head1, struct Node* head2); 
  
/* function to get the intersection point of two linked 
   lists head1 and head2 */
int getIntesectionNode(struct Node* head1, struct Node* head2) 
{ 
  int c1 = getCount(head1); 
  int c2 = getCount(head2); 
  int d; 
  
  if(c1 > c2) 
  { 
    d = c1 - c2; 
    return _getIntesectionNode(d, head1, head2); 
  } 
  else
  { 
    d = c2 - c1; 
    return _getIntesectionNode(d, head2, head1); 
  } 
} 
  
/* function to get the intersection point of two linked 
   lists head1 and head2 where head1 has d more nodes than 
   head2 */
int _getIntesectionNode(int d, struct Node* head1, struct Node* head2) 
{ 
  int i; 
  struct Node* current1 = head1; 
  struct Node* current2 = head2; 
  
  for(i = 0; i < d; i++) 
  { 
    if(current1 == NULL) 
    {  return -1; } 
    current1 = current1->next; 
  } 
  
  while(current1 !=  NULL && current2 != NULL) 
  { 
    if(current1 == current2) 
      return current1->data; 
    current1= current1->next; 
    current2= current2->next; 
  } 
  
  return -1; 
} 
  
/* Takes head pointer of the linked list and 
   returns the count of nodes in the list */
int getCount(struct Node* head) 
{ 
  struct Node* current = head; 
  int count = 0; 
  
  while (current != NULL) 
  { 
    count++; 
    current = current->next; 
  } 
  
  return count; 
} 
  
/* IGNORE THE BELOW LINES OF CODE. THESE LINES 
   ARE JUST TO QUICKLY TEST THE ABOVE FUNCTION */
int main() 
{ 
  /* 
    Create two linked lists 
  
    1st 3->6->9->15->30 
    2nd 10->15->30 
  
    15 is the intersection point 
  */
  
  struct Node* newNode; 
  struct Node* head1 = 
            (struct Node*) malloc(sizeof(struct Node)); 
  head1->data  = 10; 
  
  struct Node* head2 = 
            (struct Node*) malloc(sizeof(struct Node)); 
  head2->data  = 3; 
  
  newNode = (struct Node*) malloc (sizeof(struct Node)); 
  newNode->data = 6; 
  head2->next = newNode; 
  
  newNode = (struct Node*) malloc (sizeof(struct Node)); 
  newNode->data = 9; 
  head2->next->next = newNode; 
  
  newNode = (struct Node*) malloc (sizeof(struct Node)); 
  newNode->data = 15; 
  head1->next = newNode; 
  head2->next->next->next  = newNode; 
  
  newNode = (struct Node*) malloc (sizeof(struct Node)); 
  newNode->data = 30; 
  head1->next->next= newNode; 
  
  head1->next->next->next = NULL; 
  
  printf("\n The node of intersection is %d \n", 
          getIntesectionNode(head1, head2)); 
  
  getchar(); 
}