1206.设计跳表

链接：1206.设计跳表
难度：Hard
标签：设计、链表
简介：不使用任何库函数，设计一个跳表 。

题解 1 - cpp

• 编辑时间：2022-07-26
• 执行用时：516ms
• 内存消耗：28.1MB
• 编程语言：cpp
• 解法介绍：构造跳表。

class Node {
   public:
    int key, cnt;
    Node *next, *skip_next;
    Node(int _key) {
        key = _key;
        cnt = 1;
        next = skip_next = nullptr;
    }
};
class Skiplist {
   public:
    Node *head;
    Skiplist() { head = new Node(0); }
    bool search(int target) {
        Node *node = head->next;
        while (node && node->key < target) {
            if (node->skip_next && node->skip_next->key < target)
                node = node->skip_next;
            else
                node = node->next;
        }
        return node && node->key == target;
    }
    void add(int num) {
        Node *node = head->next, *prev = head;
        while (node && node->key < num) {
            prev = node;
            if (node->skip_next && node->skip_next->key < num)
                node = node->skip_next;
            else
                node = node->next;
        }
        if (node && node->key == num)
            node->cnt++;
        else {
            Node *next = new Node(num);
            next->next = node;
            prev->next = next;
            maintain_skip();
        }
    }
    bool erase(int num) {
        Node *node = head->next, *prev = head;
        while (node && node->key < num) {
            prev = node;
            if (node->skip_next && node->skip_next->key < num)
                node = node->skip_next;
            else
                node = node->next;
        }
        if (!node || node->key != num) return false;
        if (node->cnt > 1)
            node->cnt--;
        else {
            prev->next = node->next;
            maintain_skip();
            delete node;
        }
        return true;
    }
    void maintain_skip() {
        bool check = true;
        Node *node = head->next;
        while (node) {
            if (check && node->next && node->next->next) {
                node->skip_next = node->next->next;
            } else {
                node->skip_next = nullptr;
            }
            node = node->next;
        }
    }
};