Merge Skip Lists in O(m + n)

Question

I was asked to write an implementation to merge a skip list A of n elements with a skip list B of m elements in O (m + n) time complexity. I don't need code, just a basic explanation how I could achieve that.

I thought of looping through A, looping through B and comparing the values and then merging it into a new skip list C but that seems to be quadratic. Or am I missing something?

Answer 1

Skip lists are, by definition, sorted in some way (e.g. "in increasing numeric order" or "alphabetically by last name" or whatnot), using some total order of their element space.

For your problem, you're surely supposed to assume that both A and B are sorted the same way, and that you know what this way is, so that you can tell whether a given element from A is less than, greater than, or the same as a given element from B.

If so, then you can write a single loop that, in each iteration, compares the "next" element of each list. If the "next" element from A — call it a_i — is less than the "next" element from B, then you know that a_i doesn't appear in B and is less than any element you haven't examined yet, so you can append a_i to your result list and proceed to the next element of A. And, vice versa. (Of course, if the two elements are equal, then you simply append one and proceed to the next element of each list.)

(This isn't very specific to skip lists; you can use the same approach to merge any two sorted lists, regardless of the specific data structure used to implement those lists, as long as they're sorted the same way and you know what that way is.)