首页 > 试题广场 >

如下链表结构被称为跳表,其中-1表示INT_MIN,链表的最

[问答题]
如下链表结构被称为跳表,其中-1表示INT_MIN,链表的最小值,1表示INT_MAX,链表的最大值。

跳表具有如下性质:

(1) 由很多层结构组成

(2) 每一层都是一个有序的链表

(3) 最底层(Level 1)的链表包含了所有元素

(4) 如果一个元素出现在Level i的链表中,则它在Level i之下的链表也都会出现

(5) 每个节点包含了2个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

(6) 用实验中丢硬币的次数 K 作为元素占有的层数。

假设原始链表(即跳表的第一级)有N个节点,分析并计算跳表查询某个值的时间复杂度,并写出插入操作的代码。


这道题你会答吗?花几分钟告诉大家答案吧!