如下链表结构被称为跳表,其中-1表示INT_MIN,链表的最小值,1表示INT_MAX,链表的最大值。
跳表具有如下性质:
(1) 由很多层结构组成
(2) 每一层都是一个有序的链表
(3) 最底层(Level 1)的链表包含了所有元素
(4) 如果一个元素出现在Level i的链表中,则它在Level i之下的链表也都会出现
(5) 每个节点包含了2个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。
(6) 用实验中丢硬币的次数 K 作为元素占有的层数。
假设原始链表(即跳表的第一级)有N个节点,分析并计算跳表查询某个值的时间复杂度,并写出插入操作的代码。