April 10th, 2013, 05:16 PM

A true challenge.
I need to find an algorithm for the following problem:
Given two linked lists that intersect somewhere in the middle and merges into one list, I need to find an algorithm that finds the intersection point, with these limitations:
1. I'm not allowed to change, add or remove any data from the linked list (including its pointers).
2. I'm not allowed to use hash table (any other data starcture is acceptable  linked lists, arrays, pointers, counters).
3. given the following lists:
complexity should be O(K) (K=max{L,M})
(in the given situation, N is significantly bigger than K, therefore O(N) complexity will not be a good idea).
Is this problem have a solution?
April 12th, 2013, 03:55 PM

I can't do it in O(K) but I can do it between O(K log K) and O(K^2) with a binary tree.
I don't think it's possible to complete this with linear complexity. (But would be happy to be proven wrong)
MBirchmeier

Originally Posted by MBirchmeier
I can't do it in O(K) but I can do it between O(K log K) and O(K^2) with a binary tree.
I don't think it's possible to complete this with linear complexity. (But would be happy to be proven wrong)
MBirchmeier
I found the solution.
and you're right. It can't be done in O(k), unless you allow manipulation of the list's pointers.
can you figure out how?
Last edited by so.very.tired; May 4th, 2013 at 04:33 PM.

If you know the length of M and L (if L has a node counter, it should include the length of N) , it's really easy. Just walk down L for L.depth  M.depth, then walk both of them until you hit the common node. Depth counters are cheap if you have just one per list.
I no longer wish to be associated with this site.

Originally Posted by jwdonahue
If you know the length of M and L (if L has a node counter, it should include the length of N) , it's really easy. Just walk down L for L.depth  M.depth, then walk both of them until you hit the common node. Depth counters are cheap if you have just one per list.
if you know the length, then yes, that's pretty easy.
the thing is  you don't know the length of M and L, and any attempt to count them will cost you O(n), and we're looking for O(K).
again  you have to manipulate the pointers somehow...
Last edited by so.very.tired; May 14th, 2013 at 07:12 AM.