Слияние пропущенных списков

Question

Как я могу объединить 2 данных Skip lists (каждый с n клавишами) в один Skip List в O(n) сложность времени (наихудший случай)?

Просто ищу алгоритм - никакой конкретной реализации / языка.

Answer 1

store the two skip lists in two arrays: A,B
merge the arrays.
repeat until getting into root ('top' is a linked list containing only one element): 
   for each second entry in the skip list 'top' add a 'tag' (link 'upstairs' of the previous level)

это действительно O(n), потому что store и merge - это O(n), и в цикле вам нужно перебрать:

n+n/2+n/4+n/8+... = sigma(n/2^k) where k in (0,infinity) = 2n