合并跳过列表

Question

如何以 O(n) 时间复杂度（最差）将 2 个给定的 Skip List（每个都有 n 个键）合并为一个 Skip List案件）？

只是寻找算法 - 没有特定的实现/语言。

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)，因为存储和合并都是 O(n)，并且在循环中，您需要迭代：

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