Algorithms:Intersection point of two linked lists in Y shape

Algorithms Series

We are given two linked lists that intersect at a point and then become one. The number of nodes in each list before they intersect are unknown and they may be different (m and n say). We need an algorithm to find the intersection point. This can be shown by this image:

The simplest is to go with brute force where each node of the first is compared with every other node of the other list. The matching node pointers will lead us to the intersecting node. 

Time complexity: O (mn)             Space Complexity: O (1)

Can we use Hash Table? Yes. 

 The approach is:

1. Select the list having less number of nodes and store it in hash table.
2. Traverse the second list and check whether the same node pointer exists in the hash table.
3. If it does we get intersection point.

Time complexity: Time for creating the hash table + time for scanning the second list

O (m) + O (n)

 Space Complexity: O (n) or O (m)

Can we use stacks to solve it? Yes. The approach is as:

1. Push both the lists on stacks. The top of both will have the last element of the lists.
2.  Compare the top elements on two stacks.
1. If they are same pop them and store them.
2. If they are not, it means the common element has just popped out in previous step.
3. The value popped out in previous step can then be returned.

Time complexity:  O (m + n)                       Space complexity: O (m + n)

Can we use the first repeating number? Yes.

1.  Create an array and keep all the next pointers of both the lists in the array.
2.  In the array find the first repeating element in the array. The first repeating number is the intersection point.

Time complexity:  O (m + n)                       Space complexity: O (m + n)

Do we have any other approach? Yes by combining sorting and searching.

1.  Create an array and keep all the next pointers of first list in the array.
2.  Sort it (assume binary sort is used O (logn) ).
3. Then for each element in second list, search it in this sorted array.
1. If we find it then it is intersection point.

Time complexity:  Time for sorting + Time for searching = O (Max (mlogm, nlogn))                          

Space complexity: O (Max (m, n))

Do we have any efficient approach? Yes.

The approach is to compute lengths of the two lists in linear time. Then advance the longer list by difference in length of two lists and then start comparing.

1.  Find lengths (L1 and L2) of both the lists. O(n) + O(m) = O( Max (m, n))
2.  Take the difference (d) of the lengths. O(1)
3.  Make d steps in longer list. O(d)
4. Step in both lists in parallel until links to next node match. O (Min (m, n)).

Time complexity:  O (Max (m, n))            Space Complexity: O (1)

ListNode FindIntersectingNode(ListNode list1, ListNode list2) {   int L1=0, L2=0, diff=0;   ListNode head1 = list1, head2 = list2;   while(head1 != null) {    L1++;    head1 = head1.getNext();   }   while(head2 != null) {    L2++;    head2 = head2.getNext();   }   diff = L1 – L2;   if( L1 < L2) {     head1 = list2;     head2 = list1;     diff = L2 – L1;   }   for(int count = 0; count < diff; count++) head1 = head1.getNext();   while(head1 != null && head2 !+ null) {     if(head1 == head2) return head1.getData();     head1 = head1.getNext();     head2 = head2.getNext();   }   return null; }

Disclaimer: The images and various examples are taken from internet. I do not claim them as my own ideas. I have tried to mark the proper references but in case anything is missing please let me know.