CODEWITHSUNDEEP
algorithmdata-structuresmergeskip-lists
user550413
user550413

Reputation: 4819

Merge of Skip Lists

How can I merge 2 given Skip lists (each with n keys) into a one single Skip List in O(n) time complexity (worst case)?

Just looking for the algorithm - no particular implementation/language.

Upvotes: 6

Views: 3341

Answers (1)

amit
amit

Reputation: 178481

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)

it is indeed O(n) because store and merge are O(n), and in the loop, you need to iterate over: 

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

Upvotes: 7

Related Questions