Question

Write an algorithm for combining two skip lists in O(a + b) time, where a is the number of keys in the first list, and b is the number of keys in the second list.

Answer 1

Solution:

Let the two lists to be combined be skip_list1[a],skip_list2[b].

The number of elements are a and b respectively in each list.

The algorithm that combines the two lists is as shown below.

The list 'res' has the combined elements from the lists skip_list1 and skip_list2.

Algorithm:

1. Start
2. Declare 'res' list of size a+b;
3. Declare j <- 0
4. for i = 0 to a
   BEGIN
       res[j] <- skip_list1[i]
       j <- j+1
   END
5. for i = 0 to b
   BEGIN
       res[j] <- skip_list2[i]
       j <- j+1
   END
  
6. Stop