Finding the intersecting node from two intersecting linked lists

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?

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)

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.

Edit: See more here.

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.

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

Check last nodes of each list, If there is an intersection their last node will be same.