例题：
分析：
我们先来找一找跳表与单链表的相同点和不同点。
相同点：
跳表和单链表一样，都是由一个一个的节点组成的链表。
不同点：
①：跳表中的元素已经是排好序的（图中从小到大），而链表中的元素对顺序没有要求，可以乱序。
②：跳表中的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;
}
}
}
