Finding the intersecting node from two intersecting linked lists.

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 list before they intersect are unknown and both list may have it different i.e. List1 may have n nodes before it reaches intersection point and List2 might have m nodes before it reaches intersection point where m and n may be

• m = n,
• m < n or
• m > n

One known or easy solution is to compare every node pointer in the first list with every other node pointer in the second list by which the matching node pointers will lead us to the intersecting node. But, the time complexity in this case will O(n²) which will be high.

What is the most efficient way of finding the intersecting node?

Answer 1

If possible, you could add a 'color' field or similar to the nodes. Iterate over one of the lists, coloring the nodes as you go. Then iterate over the second list. As soon as you reach a node that is already colored, you have found the intersection.

Answer 2

Dump the contents of both lists into one hash table. first collision is your intersection.