Write a function to get the intersection point of two Linked Lists (Y Shape)

Method 1 (Brute Force)
Using 2 for loops. Outer loop will be for each node of the 1st list and inner loop will be for 2nd list. In the inner loop, check if any of nodes of 2nd list is same as the current node of first linked list. Time complexity of this method will be O(lm) where l and m are the number of nodes in two lists.Find the length of both the linked list
Find the difference in length(d)
For the longer LL, traverse d node and check the addresses with another LL

Method 2
Find the length of both the linked list
Find the difference in length(d)
For the longer LL, traverse d node and check the addresses with another LL


/* Link list node */
struct node
{
	int data;
	struct node* next;
};

int getCount(struct node* head);
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;
	 d = abs( c1 - c2);
	if(c1 > c2)
	{
	return getIntesectionNode(d, head1, head2);
	}
	else
	{
	return getIntesectionNode(d, head2, head1);
	}
}

/* function to get the intersection point of two linked
   lists*/
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)
	{
                // we are comparing the addresses not data
		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;
}

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

2 Thoughts on “Write a function to get the intersection point of two Linked Lists (Y Shape)

  1. Sunil Kanaujia on November 14, 2013 at 12:52 pm said:

    can any one explain that approach..

  2. Ideas followed here is that if the linked list are of same length, finding intersecting node is O(n), because we can check one to one node in both list, calculating length is part of doing that.

    Though the above program should handle the case when both list are of same length.

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation