I don't understand the interview candidate's solution. I don't think I will work properly. If the last 3rd node of List A and last node of List B intersects, this algorithm will not find the answer.

My solutions: Suppose length of List A is m, length of List B is n,

If space cost is more of a concern, do a O(n^2) search because it will cost constant space to find the intersect. (nested for loop)

If time is more of a concern,

1. traverse through both list to figure out the length. Identify the smaller list(suppose it's list A). cost O(m+n).

2. traverse List A, build a binary search tree with the address of pointers of the list as payload O(m log(m)).

3. Traverse through list B and search the tree for each element in list B. if found, then it's the intersection.O(n log(m)).

the general complexity is O(m+n+(m+n)log(m)) = O((m+n)log(m)). If we don't suppose A is the shorter, then the time complexity will be O((m+n)log(min(m,n)))

Suppose that the pointers are head1 and head2. Move head1 and increment a count1 till head1 reaches null. Move head2 and increment count2 till head2 reaches null. If head1 > head2 or head2 > head1, move the respective pointer to such a position in the linked list so that the length of the linked lists from there are equal. Then, start checking if both pointers point to the same node and incrementing both until that condition is met.

If they do point to the same node at some point, that is the node of intersection. Otherwise, there is no intersection.