力扣1206--跳表
1206. 设计跳表 - 力扣（LeetCode）
挑战一下hard,果然难搞
参考 跳表的原理与实现 [图解]_跳表实现-CSDN博客
代码如下：
struct Node{Node(Node* _right, Node* _down, int _val) :right(_right), down(_down), val(_val){}Node* right;Node* down;int val;
};//Node节点的类型，一个右指针，一个向下的指针
class Skiplist {
private:Node* head;const static int max_Level = 32;//最大层数vector<Node*> pathList;//插入节点的时候，遍历查找小于target的最后一个Node，存在pathList中
public:Skiplist() {head = new Node(NULL, NULL, -1);//创建一个头结点进来pathList.reserve(max_Level);//使用reserve提前分配空间，每次都自动扩展32个}bool search(int target) {Node* p = head;while(p){while(p->right && p->right->val < target)p = p->right;if(!p->right || p->right->val > target)p = p->down;elsereturn true;}return false;}void add(int num) {Node* p = head;pathList.clear();while(p){//从左往右查找，直到不小于num为止while(p->right != NULL && p->right->val < num)p = p->right;pathList.push_back(p);p = p->down;/*//如果到达边界，往下一层找//这地方放在尾部主要是为了后边插入的时候，pop_back出来，//刚好是从最底层插入，然后再往上更新if(p->right != NULL && p->right->val > num){//如果右节点的值域大于num，那么把它放入list尾部pathList.push_back(p);//更新pp = p->down;}//if(p->right == nullptr)这里是个错误，上边if代码执行之后，会执行这个if//上述代码会改变p的值，所以这里不判断p值，直接访问p->right会导致指针越界//如果是其他情况，把当前的p放入list尾部else{pathList.push_back(p);p = p->down;}*/}//第一次把插入的flag置为true,从最底层开始，肯定是要插入的。bool insert_Up = true;Node* downNode = nullptr;//用于记录更新此次插入后的节点，如果上层需要插节点，用此更新while(insert_Up && pathList.size() > 0){Node* tmpNode = pathList.back();//拿到最后一个节点pathList.pop_back();//弹出//把新节点插入当前层//建立新节点，同时更新right和downNode* insert_Node = new Node(tmpNode->right, downNode, num);//把新节点插入层中tmpNode->right = insert_Node;insert_Up = (rand() & 1 ) == 0;//每次有50%的概率需要提取到上一层}//如果需要在最上一层加层if(insert_Up){//创建一个新Node，right为head，down为上次的downNodeNode* tmpNode = new Node(nullptr, nullptr, -1);tmpNode->right = head;tmpNode->down = downNode;//更新headhead = tmpNode;}}bool erase(int num) {Node* p = head;bool seen = false;while(p){while(p->right && p->right->val < num)p = p->right;if(!p->right || p->right->val > num)p = p->down;else{seen = true;p->right = p->right->right;p = p->down;//没有这一行也可以，有的话可以加快查询}}return seen;}
};