我在试着找到最好的算法
converting an "ordinary" linked list
into an `ideal skip list`
。
其中ideal skip list的定义是,在第一级中,我们将拥有所有元素,在上面的级别中-一半以上,四分之一以上的元素...以此类推。
我正在考虑O(n)运行时,其中涉及到为原始链表中的每个节点抛出一个硬币,无论是否针对特定节点,我应该上去还是不上去,并为上层的当前节点创建另一个副本节点...最终这个算法会产生O(n),还有更好的算法吗?
问候