Your are given two Nodes which correspond to the first elements of two linked lists which are merging at some point as show on the picture below.
Write a function:
Node FindMergePoint(Node N1, Node N2)
Which will return intersection Node of these two lists in O(n) time without using extra memory.
1. Find lenghts (L1 and L2) of both list -- O(n) + O(n) = O(n)
2. Take the difference d of the lengths -- O(1)
3. Make d steps in longer list -- O(n)
4. Step in both lists in parallel until links to next node match -- O(n)
total time complexity = O(n)