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)
this is really O (n), because store and merge are O (n), and in a loop you need to iterate:
n+n/2+n/4+n/8+... = sigma(n/2^k) where k in (0,infinity) = 2n