I'm trying to find the best algorithm for
converting an "ordinary" linked list
into an `ideal skip list`
Where the definition of an
ideal skip list is that in the first level we'll have all
the elements , in the level above - half of them , the one after - quarter of them ... and so on .
I'm thinking about
O(n) run-time where involving throwing a coin for each node in
the original linked-list , whether or not for a specific node , should I go up or not , and create another duplicate node for the current node upstairs ...
Eventually this algorithm would produce O(n) , is there any better algorithm ?