Saturday, July 26, 2014

Intersection point of two linked lists


Given head pointers of two lists determine if they intersect or not? if yes, find the intersection point...


1. Very first approach is foreach node of one of the lists, traversing the other list and see if they meet the selected node. Say, if m and n are the lengths of two lists, then the algorithm is quadratic -O(mn)

2. Now, instead of nested loops, we can place one of the list nodes in a hash map, and traverse the other list and see if we hit a match. The time complexity will be O(n) with O(m) space or vice versa.

3. It can be solved in O(m+n) with O(1) space. Basically find the difference of lengths of two lists. Then move the longest node with the difference. And then traverse both nodes, and they should meet at the intersection point or one of the nodes reach their corresponding list end.

No comments:

Post a Comment