Answer to Question #276240 in C++ for zain

Question

Suppose there are two singly linked lists both of which intersect at some point and become a single linked list. The head or start pointers of both the lists are known, but the intersecting node is not known. Also, the number of nodes in each of the lists before they intersect is unknown and may be different in each list.

For example, List 1 may have 11 nodes before it reaches the intersection point, and List 2 might have 111 nodes before it reaches the point of intersection where 111 and 11 may be m = 11, 111 < 11 or 111 > 11. Give an algorithm for finding the merging point.

Answer 1

This takes O(M+N) time and O(1) space, where M and N are the total length of the linked lists. Maybe inefficient if the common part is very long (i.e. M,N >> m,n)

Therefore here is the algorithm

1. Traverse the two linked list to find M and N.
2. Get back to the heads, then traverse |M − N| nodes on the longer list.
3. Now walk in lock step and compare the nodes until you found the common ones.