1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
132
Rep Power
2

#### 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?
2. 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
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
132
Rep Power
2
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.
4. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
887
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.
5. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
132
Rep Power
2
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.