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

    Join Date
    Nov 2012
    Posts
    132
    Rep Power
    3

    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. #2
  3. I <3 ASCII
    Devshed Regular (2000 - 2499 posts)

    Join Date
    Aug 2003
    Posts
    2,400
    Rep Power
    1233
    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
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    132
    Rep Power
    3
    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 05:33 PM.
  6. #4
  7. 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.
    I no longer wish to be associated with this site.
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    132
    Rep Power
    3
    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 08:12 AM.

IMN logo majestic logo threadwatch logo seochat tools logo