例题：

分析：

我们先来找一找跳表与单链表的相同点和不同点。

相同点：

跳表和单链表一样，都是由一个一个的节点组成的链表。

不同点：

①：跳表中的元素已经是排好序的（图中从小到大），而链表中的元素对顺序没有要求，可以乱序。

②：跳表中的next指针可以有多个，可以分别指向不同的元素；而单链表只有一个next指针，只能指向离当前节点最近的元素。

不难发现，跳表在查询数据时有一个规律：

下楼梯方式查找

- 若next指针为null， 或者next指向的节点值 >= 目标值，则向下找

- 若next指针不为null， 且next指向的节点值 < 目标值，则向右找

可以先设计一个方法，根据节点值查找，并且记录所经过的节点路径：

        //查找指定节点并记录查询过程中所经过的节点
        public Node[] find(int val){
            Node curr = head;
            Node[] path = new Node[MAX];
            for(int level = MAX - 1; level >= 0; level--){  //向下找
                while (curr.next[level] != null && curr.next[level].value < val) { //向右找
                    curr = curr.next[level];
                }
                path[level] = curr;
            }
            return path;
        }

这段代码根据  curr.next[level].value < val 这个条件，我们最后找到的节点是目标节点的前一个节点，当然目标节点也可能不存在。这个方法在实现添加、删除方法时会经常用到。

注意：这里向下找的条件 和 向右找的条件是互斥的，所以不用再写一个向下找的判断逻辑

下图表示新加入一个节点

新加入节点时核心思想：

①：确定新加入节点的位置（把val当作目标查询，经过的路径就可以确定添加位置）

②：创建新节点随机高度，高度尽可能小（如果跳表的每个节点都很高，那么查询效率就低了）

③：修改新节点的next指针 和 路径节点的next指针

        static Random r = new Random();
        //随机返回 1~max 的数字
        /**
         * 从 1 开始，数字的几率逐级减半，例如 max = 4 ，让大概
         * - 50% 的几率返回 1
         * - 25% 的几率返回 2
         * - 12.5% 的几率返回 3
         * - 12.5% 的几率返回 4
         */
        static int randomLevel(int max){
            int x = 1;
            while(x < max){
                if(r.nextBoolean()){
                    return x;
                }
                x++;
            }
            return x;
        }

        //添加节点
        public void add(int num) {
            //1.确定新加入节点的位置（把val当作目标查询，经过的路径就可以确定添加位置）
            Node[] path = find(num);
            //2.创建新节点随机高度，高度尽可能小
            Node node = new Node(num);
            int level = randomLevel(MAX);
            //3.修改新节点的next指针， 路径节点的next指针
            for(int i = 0; i < level; i++){
                node.next[i] = path[i].next[i];
                path[i].next[i] = node;
            }
        }

---

完整代码：

package leetcodeup;

import java.util.Random;

public class SkipListLeetcode1206 {

    static class Skiplist {

        private static final int MAX = 10;  //节点的最大next指针数
        private final Node head = new Node(-1); //头节点

        static Random r = new Random();
        //随机返回 1~max 的数字
        /**
         * 从 1 开始，数字的几率逐级减半，例如 max = 4 ，让大概
         * - 50% 的几率返回 1
         * - 25% 的几率返回 2
         * - 12.5% 的几率返回 3
         * - 12.5% 的几率返回 4
         */
        static int randomLevel(int max){
            int x = 1;
            while(x < max){
                if(r.nextBoolean()){
                    return x;
                }
                x++;
            }
            return x;
        }

        static class Node{
            int value;
            Node[] next = new Node[MAX];

            public Node(int value) {
                this.value = value;
            }
        }

        //查找指定节点并记录查询过程中所经过的节点
        public Node[] find(int val){
            Node curr = head;
            Node[] path = new Node[MAX];
            for(int level = MAX - 1; level >= 0; level--){  //向下找
                while (curr.next[level] != null && curr.next[level].value < val) { //向右找
                    curr = curr.next[level];
                }
                path[level] = curr;
            }
            return path;
        }

        //查找节点
        public boolean search(int target) {
            Node[] path = find(target);
            Node node = path[0].next[0];
            return node != null && node.value == target;
        }

        //添加节点
        public void add(int num) {
            //1.确定新加入节点的位置（把val当作目标查询，经过的路径就可以确定添加位置）
            Node[] path = find(num);
            //2.创建新节点随机高度，高度尽可能小
            Node node = new Node(num);
            int level = randomLevel(MAX);
            //3.修改新节点的next指针， 路径节点的next指针
            for(int i = 0; i < level; i++){
                node.next[i] = path[i].next[i];
                path[i].next[i] = node;
            }
        }

        //删除节点
        public boolean erase(int num) {
            Node[] path = find(num);
            Node node = path[0].next[0];
            //要删除的节点可能不存在
            if(node == null || node.value != num){
                return false;
            }
            //节点存在，开始删除节点
            for(int i = 0; i < MAX; i++){
                if(path[i].next[i] != node){
                    break;
                }
                path[i].next[i] = node.next[i];
            }
            return true;
        }
    }
}