1206.md

1206. Design Skiplist

Solution 1

class Node(object):
    def __init__(self, val, next, down):
        self.val = val
        self.next = next
        self.down = down

class Skiplist(object):

    def __init__(self):
        self.head = Node(-1, None, None)

    def search(self, target):
        """
        :type target: int
        :rtype: bool
        """
        p = self.head
        while p:
            while p.next and p.next.val < target:
                p = p.next
            if p.next and p.next.val == target:
                return True
            p = p.down
        return False

    def add(self, num):
        """
        :type num: int
        :rtype: None
        """
        stack = []
        p = self.head
        while p:
            while p.next and p.next.val < num:
                p = p.next
            stack.append(p)
            p = p.down
        insert = True
        down = None
        while insert and stack:
            p = stack.pop()
            p.next = Node(num, p.next, down)
            down = p.next
            insert = random.random() < 0.5
        if insert:
            self.head = Node(-1, None, self.head)

    def erase(self, num):
        """
        :type num: int
        :rtype: bool
        """
        p = self.head
        ret = False
        while p:
            while p.next and p.next.val < num:
                p = p.next
            if p.next and p.next.val == num:
                ret = True
                p.next = p.next.next
            p = p.down
        return ret

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)