Finding the intersecting node from two intersecting linked lists
Dump the contents (or address) of both lists into one hash table. first collision is your intersection.
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.
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)
- Traverse the two linked list to find M and N.
- Get back to the heads, then traverse |M − N| nodes on the longer list.
- Now walk in lock step and compare the nodes until you found the common ones.
Edit: See more here.