var Skiplist = function() {
this.head = new Node()
};
/**
* @param {number} target
* @return {boolean}
*/
Skiplist.prototype.search = function(target) {
let head = this.head;
while(head) {
// 找到小于目标值得最上层的最大值
while(head.next && head.next.val < target) {
head = head.next;
}
// 如果找到了目标值，直接返回
if (head.next && head.next.val == target) {
return true
}
// 将指针下移
head = head.down;
}
return false;
};
/**
* @param {number} num
* @return {void}
*/
Skiplist.prototype.add = function(num) {
let list = [], head = this.head;
while(head) {
while(head.next && head.next.val < num) {
head = head.next;
}
list.push(head);
head = head.down;
}
let insertUp = true, downNode = null;
while(insertUp && list.length) {
head = list.pop()
head.next = new Node(num, head.next, downNode)
downNode = head.next;
insertUp = (Math.random() > 0.5)
}
if (insertUp) {
this.head = new Node(-1, null, this.head)
}
};
/**
* @param {number} num
* @return {boolean}
*/
Skiplist.prototype.erase = function(num) {
let head = this.head;
let found = false;
while(head) {
while(head.next && head.next.val < num) {
head = head.next;
}
if (head.next && head.next.val == num) {
head.next = head.next.next;
found = true;
}
head = head.down;
}
return found;
};
function Node(val = -1, next = null, down = null) {
this.val = val;
this.next = next;
this.down = down;
}