Building ideal skip lists

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?

• Could you please reformat the question? – Dave Clarke Apr 30 '12 at 13:14
• Hint: what is the relationship between a skip list and a binary tree? – AProgrammer Apr 30 '12 at 13:46
• @AProgrammer: I didn't learn yet binary trees , so I can't use it – JAN Apr 30 '12 at 13:48
• Please, try to ask only one question at a time. If you want to ask two unrelated questions, post two different questions. – svick Apr 30 '12 at 14:25
• Welcome to Stack Exchange. This is a questions and answers site. If you have two separate questions (even if they're about related topics), please ask them separarely. I've edited out your second question, which wasn't very usefully formulated. Please ask it in a separate post, but you should say what you've already tried and what kind of improvement you're expecting. – Gilles Apr 30 '12 at 22:28

• For every item, flip a coin until you get a $0$. The item's level is the number of $1$s you got; create the tower of pointers and link already created towers accordingly.
For every item, the expected level is $\frac{1}{p}$ with $p$ the probability of a $1$ (geometric distribution); therefore, every item causes constant runtime in expectation, resulting in a total expected runtime in $O(n)$ for creating the list. As the maximum level is $\log_{1/p} n$ in expectation and you only need to remember the last (dangling) pointer for every level, the algorithm requires only $O(\log_{1/p} n)$ additional memory in expectation.
It is clear that there can be no algorithm that works in expected time $o(n)$; in expectation, there have to be $\frac{n}{2}$ items on level two so at least that many have to be investigated (in expectation).