1206. 设计跳表（设计题 - 参考 Redis 中的实现）

LeetCode： 1206. 设计跳表

做题之前，首先理解跳表是什么东西： 深入理解跳跃链表[一]

根据大佬的代码抄了一遍 ： 设计跳表 - 参考 Redis 中的实现

思路： >> 待补

设计跳表 - 参考 Redis 中的实现

class Skiplist {
    private static final float SKIPLIST_P = 0.5f;
    private static final int MAX_LEVEL = 16;

    Node head;

    class Node{
        int val;
        Node pre; // 后退指针
        Node[] next; // 前进指针

        public Node(int val){
            this.val = val;
            next = new Node[randomLevel()];
        }

        public Node(int val, int size){
            this.val = val;
            next = new Node[size + 1];
        }

        private int randomLevel(){
            int level = 1;
            while(Math.random() < SKIPLIST_P && level < MAX_LEVEL){
                level++;
            }
            return level;
        }

    }

    public Skiplist() {
        head = new Node(-1, MAX_LEVEL);
    }
    
    public boolean search(int target) {
        Node p = searchNode(target);
        return p.val == target;
    }
    
    public void add(int num) {
        Node p = searchNode(num);
        Node n = new Node(num);
        n.pre = p;
        for(int i = 0; i < n.next.length; i++){
            Node f = p;
            while(f.pre != null && f.next.length < i + 1){
                f = f.pre;
            }
            if(i == 0 && f.next[i] != null) {
                f.next[i].pre = n;
            }
            n.next[i] = f.next[i];
            f.next[i] = n;
        }

    }
    
    public boolean erase(int num) {
        if(isEmpty()) return false;
        Node p = searchNode(num);
        if(p.val != num) return false;
         for(int i = 0; i < p.next.length; i++){
            Node f = p.pre;
            while(f.pre != null && f.next.length < i + 1) {
                f = f.pre;
            }
            if(i == 0 && f.next[i].next[i] != null){
                f.next[i].next[i].pre = f;
            }
            f.next[i] = f.next[i].next[i];
        }
        return true;
    }

    private Node searchNode(int num){
        if(isEmpty()) return head;
        Node p = head;
        for(int i = MAX_LEVEL; i >= 0; i--){
            while(p.next[i] != null && p.next[i].val <= num){
                p = p.next[i];
            }
        }
        return p;
    }

    private boolean isEmpty(){
        return head.next[0] == null;
    }
}

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist obj = new Skiplist();
 * boolean param_1 = obj.search(target);
 * obj.add(num);
 * boolean param_3 = obj.erase(num);
 */