CareerCup

ydxr's approach is good but requires O(n) memory. If you are short on memory [interviewers usually ask the classic trade-off alternative i.e. performance/extra computation over memory]

Assuming the size of list is not maintained in the list data structure.

1) Traverse the first list & determine its size lets say szList1.
2) Traverse the 2nd list & determine its size lets say szList2.
3) Find the difference in the size of the list. difference = szList1 - szList2;
4) Once you have the difference, iterate the 1st list or 2nd list for 'difference' number of nodes [if difference < 0, iterate list2 else iterate list1].Intersection will start only after the 'difference' number of nodes. Say if difference = 3, intersection can be at 4th node,..... to Nth node.
5) Once you reach difference number of nodes, break out of the loop.
6) Now both lists have same number of elements to be iterated. In another loop iterate both lists and compare their nodes. You can get the intersection.

Running time = O(n) + O(m) + O( greaterof(n,m))
Worst case = Last element of both lists are same i.e
2O(n) + O(m) if n > m else
2O(m) + O(n) if m > n

Memory = O(1)

Scan through the first list and insert each node pointer into a hashmap. Now for each node pointer of the second list check if it is in the hashmap. If the pointer is present in the hashmap then its the point at which they merge. This will take O(n) time.

@Hercules : Are you assuming that the lists are sorted. If no, I dont get your solution. Why would the intersection start only after difference number of nodes. Lists could be like :

1->2->3.

6->3->5->8->6
In this case your answer would be the lists dont intersect ? Could you please explain your approach in a bit detailed way ?

@Sam
In this case the node with value 3 would not be like a node of Singly linked list. Either 3's next can be 5 or NULL, but not both.

Hercules: Big O notation.
if n > m, the algorithm takes n+m+max(n+m), the the algorithm is O(n) not O(n)+O(m)+O(max(n,m)).
2 x O(n) is still O(n).
Your algorithm may not work if they merge at some point then seperate again or they start at the same and then seperate.

Say: 1->2->3->4->5->6
and 7->3->4->8->9->10
and the number of nodes are all 6.

Or say: 1->2->3->4->5->6
and 1->2->7->8->9->10
and the number of nodes are all 6.

I have a sol in linear order of n,m

As Ravi mentioned find out the list which is shorter from the merge pt (can be done by computing the individual lengths and then taking the difference)
So for first list the length is
x + z
for second list its
y + z.
Total lenght x + y + 2z (1)

Now reverse the list which is shorter (say it started from head2 ).

Now if you traverse the list from head 1, u will reach head 2. (Draw the diagram and it would be clear )
The lenght now would be x + y. (2)
Using 1, 2 you can compute the z and the pt where they merge.

I have a sol in linear order of n,m

As Ravi mentioned find out the list which is shorter from the merge pt (can be done by computing the individual lengths and then taking the difference)
So for first list the length is
x + z
for second list its
y + z.
Total lenght x + y + 2z (1)

Now reverse the list which is shorter (say it started from head2 ).

Now if you traverse the list from head 1, u will reach head 2. (Draw the diagram and it would be clear )
The lenght now would be x + y. (2)
Using 1, 2 you can compute the z and the pt where they merge.

How abt this solution?

1. Reverse the list 1
2. Reverse the list 2
3. Then start comparing each node of list 1 with list 2 till min(l1.size,l2.size).The prev node at which the differ is the merging point..

How abt this solution?

1. Reverse the list 1
2. Reverse the list 2
3. Then start comparing each node of list 1 with list 2 till min(l1.size,l2.size).The prev node at which the differ is the merging point..