Write a function to get the intersection point of two Linked Lists

  • Intersection point means end of one linked list is linked with some node in another linked list.
 data- linked-list

Given two Linked Lists, create intersection lists that contain intersection of the elements present in the given lists.

Example

Input:
   List1: 20->25->4->30
   lsit2:  8->4->2->20
Output:
   Intersection List: 4->20
Markdown

Sample Code in C:

/ 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(); 
} 
C

Code Explanation :

  • Get count of the nodes in the first list, let count be c1.
  • Get count of the nodes in the second list, let count be c2.
  • Get the difference of counts d = abs (c1 – c2)
  • Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
  • Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

Time Complexity: O(m+n)
Auxiliary Space: O(1)

Output :

The node of intersection is 15

Categorized in:

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,