题目描述
LeetCode 1206 设计跳表 https://leetcode-cn.com/problems/design-skiplist/
C++ 代码
struct node
{
int val;
node* right;
node* down;
node(int v, node* r, node* d) : val(v), right(r), down(d){}
};
class Skiplist
{
public:
node* head;
Skiplist()
{
head = new node(-1, nullptr, nullptr);
}
bool search(int target)
{
node* p = head;
while (p)
{
if (p->val == target) //找到目标值
return true;
if (p->right && p->right->val <= target) //右侧结点的值小于或等于目标值,指针右移
p = p->right;
else if (!p->right || p->right->val > target) //右侧结点为空或大于目标值,指针下移
p = p->down;
}
return false;
}
void add(int num)
{
vector<node*> d; //记录向下走的位置
node* p = head;
while (p)
{
if (p->right && p->right->val <= num) //右侧结点的值小于或等于目标值,指针右移
p = p->right;
else if (!p->right || p->right->val > num) //右侧结点为空或大于目标值,指针下移
{
d.push_back(p); //记录下向下走的位置
p = p->down;
}
}
int isInsert = 1; //是否插入该结点
node* downNode = nullptr; //记录新插入的结点的地址,往上插入时更新down
while (isInsert && d.size()) //d不空并且这一层可以插入该结点时
{
node* p = d.back(); //从后往前遍历d
d.pop_back();
p->right = new node(num, p->right, downNode); //插入新的结点,更新downNode和isInsert
downNode = p->right;
isInsert = rand() % 2;
}
if (isInsert) //增加新层
{
node* nlevel = new node(num, nullptr, downNode);
node* nhead = new node(-1, nlevel, head);
head = nhead;
}
}
bool erase(int num)
{
node* p = head;
bool f = false;
while (p)
{
while (p && p->right && p->right->val == num) //找到目标值,删除结点,释放(要把整列都删除)
{
node* n = p->right;
p->right = p->right->right;
p = p->down;
delete n;
f = true;
}
if (p && p->right && p->right->val < num) //右侧结点的值小于目标值,指针右移
p = p->right;
else if (p && (!p->right || p->right->val > num)) //右侧结点为空或大于目标值,指针下移
p = p->down;
}
return f;
}
};