ALGO PLANET

Intersection of two linked lists

Problem statement

We consider a linked list where each node has the following data structure:

	
	struct ListNode
	{
		int val;
		ListNode *next;
		ListNode(int x) : val(x), next(NULL){}
	};

We consider two linked lists L1 and L2. The goal is to determine if there is an intersection between L1 and L2. The following figure represents an example of intersection of two linked lists.

Indeed, both lists share the same nodes from c1 to c3.
Given the following prototype of the function:

	
	ListNode* getIntersectionNode(ListNode *headA, ListNode *headB);

the objective is to propose an algorithm with a time complexity of O(n) and a memory complexity of O(1).
If there is no intersection between both lists, the function must return NULL.
Finally we assume that there are no cycles in both lists.
Before delving into the reasonning, I invite you to try to solve this solution and to come back after a while ;)

First reasonning

Let see the first solution that comes into mind without taking care about the requirements. An easy solution would be for each node of a list to explore all the nodes of the other list and test if they are equal:

	
	  ListNode* getIntersectionNode(ListNode *headA, ListNode *headB)
	  {
	      if(headA == NULL || headB == NULL)
	          return NULL;

	      for(ListNode * tempA = headA; tempA != NULL; tempA = tempA->next)
	      {
	          for(ListNode * tempB = headB; tempB != NULL; tempB = tempB->next)
              {
	              if(tempA == tempB)
                     return tempA;
              }
	      }
          return NULL;
	  }

This solution is O(1) memory complexity but the time complexity in the worst and average case is O(n*m) if n is the size of the first list and m the size of the second list. This proposed solution does not fulfill the requirements.

Second reasonning

I repeat here what is important is not to code the solution but how we find the solution. The requirement is that the time complexity has to be in linear time and the memory complexity has to be constant.
So the solution is more or less similar to an algorithm that finds the intersection in one scan of the nodes of one of the list.
The first idea that comes into mind is to start with two pointers targeting the first nodes of both lists and then comparing side-by-side the nodes in parallel until we reach the end of the lists. You will tell me that is not so clever because if the lists have different size (and it is the general case) it will not work. I completely agree but it is the starting point of the good solution !
Indeed, if I find the starting nodes for both lists where I am sure that the number of the remaining nodes to scan is the same then I can do the solution I just described before. The following figure will help you to understand. If we start with a2 from L1 and b1 from L2 then we just have to scan the remaining nodes of both lists in parallel until both nodes are equal. For example in the figure above, we will first compare a2 and b1, a3 and b2 and c1 and c1. We stop and we return c1.
Ok great but the question now is how to determine the starting nodes ?
I think by looking at the figure you guess how to do it right ? Indeed, if we know the size of both lists and then compare these sizes we know where to start.

If m = n, the starting nodes are simply the first nodes of both lists.
If n > m then the starting nodes are the (n-m)^th of the first list and the first node of the second list.
If m > n then the starting nodes are the (m-n)^th of the second list and the first node of the first list.

It is time to analyse the time complexity of our solution in the worst case. Determining the size of both lists is achieved in linear time by simply scanning all the nodes of each list. Going to the starting nodes is achieved in linear time in the worst case (if we have to go to the last node of one list). Finally, comparing the nodes is also achieved in linear time. It seems that this solution fulfills the requirements :).
I am a nice guy, here is the source code:

	
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
{
        if(headA == NULL || headB == NULL)
            return NULL;
        
        int countA = 0, countB = 0;
        ListNode * tempA = headA;
        ListNode * tempB = headB;
        
        for(; tempA != NULL; tempA = tempA->next)
            countA++;
        for(; tempB != NULL; tempB = tempB->next)
            countB++;
            
        tempA = headA;
        tempB = headB;
        
        if(countA != countB)
        {
            if(countA > countB)
            {
                for(int i=0; i< countA - countB; ++i)
                    tempA = tempA->next;
            }
            else
            {
                for(int i=0; i< countB - countA; ++i)
                    tempB = tempB->next;
            }
        }
        
        while(tempA != NULL && tempB !=NULL)
        {
		  if(tempA == tempB)
		    return tempA;

            tempA = tempA->next;
            tempB = tempB->next;
        }
        return NULL;
    }

Conclusion

I really hope you had fun tackling this problem. If you find a more elegant solution (and it is great !) do not hesitate to send me a message with your solution. It will be a pleasure for me to add it in this page with your name, your website link and/or your github link.