I'm trying to find the best algorithm for converting an ordinary linked list into an ideal skip list. The definition of an ideal skip list is that in the first level we'll have all the elements, half of them in the next level, a quarter of them in the level after that, and so on.I'm thinking about a $\mathcal{O}(n)$ run-time algorithm involving throwing a coin for each node in the original linked-list, to determine for any given node whether it should be placed in a higher or lower level, and create a duplicate node for the current node at a higher level. This algorithm should work in $\mathcal{O}(n)$; is there any better algorithm? 
Building ideal skip lists
algorithms;data structures;randomized algorithms;lists