LeetCode 题解工作台
设计跳表
不使用任何库函数，设计一个 跳表 。 跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。 例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80 、 …
2
题型
5
代码语言
3
相关题
当前训练重点
困难 · 链表指针操作
答案摘要
跳表的核心思想是使用多个“层级”来存储数据，每一层都相当于一个索引。数据从底层的链表开始逐渐上升到更高层级的链表，最终形成一个多层链表结构。每一层的节点只包含部分数据，这样就可以通过跳跃来减少查找的时间。 在这个问题中，我们使用一个 类来表示跳表的节点，每个节点包含一个 域和一个 数组，数组的长度为 ，表示当前节点在每一层的下一个节点。我们使用一个 类来实现跳表的操作。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
不使用任何库函数，设计一个 跳表 。
跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。
例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：
跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。
了解更多 : https://oi-wiki.org/ds/skiplist/
在本题中，你的设计应该要包含这些函数：
bool search(int target): 返回target是否存在于跳表中。void add(int num): 插入一个元素到跳表。bool erase(int num): 在跳表中删除一个值，如果num不存在，直接返回false. 如果存在多个num，删除其中任意一个即可。
注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。
示例 1:
输入 ["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"] [[], [1], [2], [3], [0], [4], [1], [0], [1], [1]] 输出 [null, null, null, null, false, null, true, false, true, false] 解释 Skiplist skiplist = new Skiplist(); skiplist.add(1); skiplist.add(2); skiplist.add(3); skiplist.search(0); // 返回 false skiplist.add(4); skiplist.search(1); // 返回 true skiplist.erase(0); // 返回 false，0 不在跳表中 skiplist.erase(1); // 返回 true skiplist.search(1); // 返回 false，1 已被擦除
提示:
0 <= num, target <= 2 * 104- 调用
search,add,erase操作次数不大于5 * 104
解题思路
方法一：数据结构
跳表的核心思想是使用多个“层级”来存储数据，每一层都相当于一个索引。数据从底层的链表开始逐渐上升到更高层级的链表，最终形成一个多层链表结构。每一层的节点只包含部分数据，这样就可以通过跳跃来减少查找的时间。
在这个问题中，我们使用一个 类来表示跳表的节点，每个节点包含一个 域和一个 数组，数组的长度为 ，表示当前节点在每一层的下一个节点。我们使用一个 类来实现跳表的操作。
跳表包含一个头节点 和当前的最大层数 。头节点的值设为 ，用于标识链表的起始位置。我们使用一个动态数组 来存储指向后继节点的指针。
对于 操作，我们从跳表的最高层开始，逐层向下遍历，直到找到目标节点或者确定目标节点不存在。每层都通过 方法跳跃到最接近目标的节点。
对于 操作，我们首先随机决定新节点的层数。然后，从最高层开始，逐层找到每层中最接近新值的节点，并在相应位置插入新节点。如果插入的层数大于当前跳表的最大层数，我们需要更新跳表的层数。
对于 操作，类似于查找操作，遍历跳表的每一层，找到需要删除的节点并删除它。删除节点时需要更新每一层的 指针。如果跳表的最高层没有节点，则需要减少跳表的层数。
另外，我们定义了一个 方法来随机决定新节点的层数。该方法会生成一个 之间的随机数，直到生成的随机数大于等于 为止。还有一个 方法用于查找每一层中最接近目标值的节点。
上述操作的时间复杂度为 ，其中 为跳表的节点数。空间复杂度为 。
class Node:
__slots__ = ['val', 'next']
def __init__(self, val: int, level: int):
self.val = val
self.next = [None] * level
class Skiplist:
max_level = 32
p = 0.25
def __init__(self):
self.head = Node(-1, self.max_level)
self.level = 0
def search(self, target: int) -> bool:
curr = self.head
for i in range(self.level - 1, -1, -1):
curr = self.find_closest(curr, i, target)
if curr.next[i] and curr.next[i].val == target:
return True
return False
def add(self, num: int) -> None:
curr = self.head
level = self.random_level()
node = Node(num, level)
self.level = max(self.level, level)
for i in range(self.level - 1, -1, -1):
curr = self.find_closest(curr, i, num)
if i < level:
node.next[i] = curr.next[i]
curr.next[i] = node
def erase(self, num: int) -> bool:
curr = self.head
ok = False
for i in range(self.level - 1, -1, -1):
curr = self.find_closest(curr, i, num)
if curr.next[i] and curr.next[i].val == num:
curr.next[i] = curr.next[i].next[i]
ok = True
while self.level > 1 and self.head.next[self.level - 1] is None:
self.level -= 1
return ok
def find_closest(self, curr: Node, level: int, target: int) -> Node:
while curr.next[level] and curr.next[level].val < target:
curr = curr.next[level]
return curr
def random_level(self) -> int:
level = 1
while level < self.max_level and random.random() < self.p:
level += 1
return level
# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log n) expected for search, add, and erase due to randomized level heights and top-down traversal. Space complexity depends on the number of nodes and levels, typically O(n log n) in expectation, because each node stores multiple forward pointers. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate correctly identifies layered linked-list pointer manipulation.
- question_mark
Handles random level assignment for nodes and explains expected performance.
- question_mark
Properly updates forward pointers during insertions and deletions without errors.
常见陷阱
外企场景- error
Incorrectly updating forward pointers leading to broken links.
- error
Neglecting randomization for node levels, causing linear-time operations.
- error
Failing to handle edge cases like duplicate values or non-existent elements during erase.
进阶变体
外企场景- arrow_right_alt
Implement Skiplist with custom probability for level promotion to optimize for search-heavy workloads.
- arrow_right_alt
Support range search queries using additional pointers or skip pointers within levels.
- arrow_right_alt
Design a persistent Skiplist that preserves previous versions while allowing insertions and deletions.