跳過列表的合併

Question

如何合併2個給定的Skip lists（每個都帶有n個密鑰）合併爲一個Skip ListO(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），因爲存儲和合並是O（N），並在循環中，你需要遍歷：

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