Ideal Skip list ? O(n) run-time?

Question

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 ?

Regards

Answer 1

I am assuming the linked list is sorted - otherwise it cannot be done in comparison based algorithm, since you need to sort it in Omega(nlogn)

• Iterate on the "highest level" of the list, and add a "link up node" every second node.
• Repeat until the highest level has only one node.

The idea is to generate a new list, half the size of the original, which is linked to the original in every 2nd link, and then recursively invoke on the smaller list, until you reach a list of size 1.
You will end up with lists of size 1,2,4,...,n/2 linked to each other.

pseudo code:

makeSkipList(list):
  if (list == null || list.next == null): //stop clause - a list of size 1
      return
//root is the next level list, which will have n/2 elements.
  root <- new link node
  root.linkedNode <- list //linked node is linking "down" in the skip list.
  root.next <- null //next is linking "right" in the skip list.
  lastLinkNode <- root
  i <- 1
//we create a link every second element
  for each node in list, exlude the first element:
     if (i++ %2 == 0): //for every 2nd element, create a link node.
         lastLinkNode.next <- new link node 
         lastLinkNode <- lastLinkNode.next //setting the "down" field to the element in the list
         lastLinkNode.linkedNode <- node 
         lastLinkNode.next <- null
   makeSkipList(root) //recursively invoke on the new list, which is of size n/2.

Complexity is O(n) since the algorithm complexity can be described as T(n) = n + T(n/2), thus you get T(n) = n + n/2 + n/4 + ... -> 2n

It is easy to see it cannot be done better then O(n), because at the very least you will have to add at least one node in the second half of the original list, and getting there is itself O(n)