3 ms·

traversing them won't get you O(log(m+n)) complexity.

• bjornsing 5y ago
  If they truly are lists (i.e. not random access) then nothing will give you that. If you have the head elements of the lists and you want the median then you have to traverse (m+n)/2 elements just to get to the median. There is no way around that. If you translate the lists to arrays then that’s an o(n+m) operation in itself.
  • erwald 5y ago
    ah yes, of course, that was a misreading on my part, sorry. the title is somewhat misleading, but if you go have a look at the original problem you see that it provides as inputs random-access arrays, not linked lists. i only changed them to lists in the initial, naïve solution in order to keep things simple at first.