LeetCode 1206. 设计跳表

2026-08-25 HGNULB 约 9 分钟

文章信息 12 个分类 2 个标签

分类

LeetCode CodeTop 困难未解决 10-20 腾讯字节阿里微软美团滴滴虾皮

题目描述

✅ 1206. 设计跳表

题意分析

实现跳表，支持查找某个值是否存在、插入一个值，以及删除某个值的一次出现。查找返回是否找到，删除在找到并移除一个节点时返回 true，值不存在时返回 false。

重复值是合法的，每次插入都增加一个独立节点，删除时只移除其中一个。不能用不允许重复的集合替代，也不能一次删除所有相同值。

跳表要通过自己维护的多层链表加速操作，目标是期望对数时间。随机性用于决定索引层次，不影响查找和删除的正确性；不能直接调用现成的有序容器代替跳表实现。

解法：多层有序链表 + 前驱数组

核心思路

[!blue]

底层是一条包含全部节点的有序链表，高层只保留底层中的一部分节点，相当于跨过多个底层节点的快捷通道。一个层高为 h 的节点拥有 next[0..h-1]，分别指向各层的后继；它出现在第 i 层时，也一定出现在更低的所有层。头哨兵覆盖全部层，统一处理链表开头的插入和删除。

查找从当前最高层的头部开始，只要右侧节点的值严格小于目标，就向右走；右侧为空或不再小于目标，就下降一层。高层越过的节点都小于目标，下降后只需从当前位置继续补查高层跳过的细节，不必回到头部。最终在底层停下时，当前位置就是严格小于目标的最后一个节点，其后继才可能等于目标。

插入和删除都需要知道每一层应修改哪条指针，因此下降前把当前位置保存到 update[i]。search 只检查 update[0] 的后继；add 和 erase 则复用同一条查找路径得到的前驱数组。

插入时随机生成新节点层高：从一层开始，每次以二分之一概率再增加一层，最多 32 层。若新节点超过当前有效层数，新增各层之前没有普通节点，其前驱就是头哨兵。在节点覆盖的每层，先让新节点指向前驱的旧后继，再让前驱指向新节点，完成普通单链表的插入。因为每层都接在小于目标和不小于目标之间，各层仍保持有序。

查找前驱使用严格小于，所以同值节点总是插在已有同值节点之前。删除时，先选底层第一个等于目标值的具体节点；在这个节点参与的每一层，它也一定排在其他同值节点之前，因此 update[i] 的后继就是它，可以直接绕过它。它未参与的更高层不能修改，因为那里的同值节点可能是另一个副本。删除后如果最高层已经为空，就逐层降低有效层数，底层至少保留一层。

随机提升使节点出现在第 i 层的概率约为 1/2^i，越高的层越稀疏。查找先用稀疏层跨过大段区间，再向下定位，得到期望对数时间；每个节点平均只有不到两条前进指针，所以总索引空间为线性。若随机层高极端失衡，操作仍可能退化为线性，但结果不会因此出错。

解题步骤

初始化有 32 层指针的头哨兵，将当前有效层数 level 设为一。

findPredecessors(target) 从高层向下搜索，每层尽量右移到最后一个小于目标的节点，并把它记录到 update。

search(target) 检查底层前驱的后继是否存在且值等于目标。

add(num) 先取得前驱数组，再生成节点层高；超出现有高度时补齐新层前驱为头哨兵，并更新有效层数。

创建新节点，在它拥有的每层依次连接旧后继与前驱。即使值已存在，也照常插入一个新节点。

erase(num) 先确认底层目标存在，再仅从目标节点拥有的各层摘除该节点。

删除后收缩空的最高层，至少保留一层；返回删除是否成功。

代码实现

class Skiplist {
    private static final int MAX_LEVEL = 32;
    private final Node head = new Node(-1, MAX_LEVEL);
    private int level = 1;

    public boolean search(int target) {
        Node candidate = findPredecessors(target)[0].next[0];

        return candidate != null && candidate.value == target;
    }

    public void add(int num) {
        Node[] update = findPredecessors(num);
        int nodeLevel = randomLevel();

        if (nodeLevel > level) {
            for (int i = level; i < nodeLevel; i++) {
                // 新增层还没有普通节点，其前驱只能是头哨兵。
                update[i] = head;
            }

            level = nodeLevel;
        }

        Node node = new Node(num, nodeLevel);

        for (int i = 0; i < nodeLevel; i++) {
            // 先接旧后继，再让前驱接入新节点，避免形成自环。
            node.next[i] = update[i].next[i];
            update[i].next[i] = node;
        }
    }

    public boolean erase(int num) {
        Node[] update = findPredecessors(num);
        Node target = update[0].next[0];

        if (target == null || target.value != num) {
            return false;
        }

        // 只摘除这个目标节点实际拥有的层，保留其他同值节点。
        for (int i = 0; i < target.next.length; i++) {
            update[i].next[i] = target.next[i];
        }

        while (level > 1 && head.next[level - 1] == null) {
            level--;
        }

        return true;
    }

    private Node[] findPredecessors(int target) {
        Node[] update = new Node[MAX_LEVEL];
        Node current = head;

        for (int i = level - 1; i >= 0; i--) {
            while (current.next[i] != null && current.next[i].value < target) {
                current = current.next[i];
            }

            update[i] = current;
        }

        return update;
    }

    private int randomLevel() {
        int nodeLevel = 1;

        while (nodeLevel < MAX_LEVEL
                && java.util.concurrent.ThreadLocalRandom.current().nextBoolean()) {
            nodeLevel++;
        }

        return nodeLevel;
    }

    private static class Node {
        final int value;
        final Node[] next;

        Node(int value, int level) {
            this.value = value;
            this.next = new Node[level];
        }
    }
}

import "math/rand"

const maxSkipLevel = 32

type skipNode struct {
    value int
    next  []*skipNode
}

type Skiplist struct {
    head  *skipNode
    level int
}

func Constructor() Skiplist {
    return Skiplist{
        head:  &skipNode{value: -1, next: make([]*skipNode, maxSkipLevel)},
        level: 1,
    }
}

func (s *Skiplist) Search(target int) bool {
    candidate := s.findPredecessors(target)[0].next[0]
    return candidate != nil && candidate.value == target
}

func (s *Skiplist) Add(num int) {
    update := s.findPredecessors(num)
    nodeLevel := randomLevel()
    if nodeLevel > s.level {
        for i := s.level; i < nodeLevel; i++ {
            // 新增层还没有普通节点，其前驱只能是头哨兵。
            update[i] = s.head
        }
        s.level = nodeLevel
    }

    node := &skipNode{value: num, next: make([]*skipNode, nodeLevel)}
    for i := 0; i < nodeLevel; i++ {
        // 先接旧后继，再让前驱接入新节点，避免形成自环。
        node.next[i] = update[i].next[i]
        update[i].next[i] = node
    }
}

func (s *Skiplist) Erase(num int) bool {
    update := s.findPredecessors(num)
    target := update[0].next[0]
    if target == nil || target.value != num {
        return false
    }

    // 只摘除这个目标节点实际拥有的层，保留其他同值节点。
    for i := 0; i < len(target.next); i++ {
        update[i].next[i] = target.next[i]
    }
    for s.level > 1 && s.head.next[s.level-1] == nil {
        s.level--
    }
    return true
}

func (s *Skiplist) findPredecessors(target int) []*skipNode {
    update := make([]*skipNode, maxSkipLevel)
    current := s.head
    for i := s.level - 1; i >= 0; i-- {
        for current.next[i] != nil && current.next[i].value < target {
            current = current.next[i]
        }
        update[i] = current
    }
    return update
}

func randomLevel() int {
    level := 1
    for level < maxSkipLevel && rand.Intn(2) == 1 {
        level++
    }
    return level
}

复杂度分析

时间复杂度：在本题数据规模下，search、add、erase 的期望时间均为 O(log n)，其中 n 是当前节点数，重复值的每次出现都单独计入。随机层次不平衡时最坏为 O(n)；固定的 32 层上限适用于本题规模。

空间复杂度：期望 O(n)。各层节点数量按约一半递减，每个节点平均只保存常数条前进指针；单次操作的前驱数组固定最多 32 项。

关键点总结

[!green]

高层是低层的有序子序列，允许查找跨越节点后从当前位置向下细化。

前驱数组记录每层待修改的链接位置，让插入与删除各自只需一次查找。

严格小于目标的比较统一了插入位置、查询候选和重复节点的删除对象。

随机层高只决定性能，不决定答案；有序关系与节点指针才保证操作正确。

删除一个副本只摘除同一个节点在各层的出现，不应按相同数值批量删除。

易错点总结

[!yellow]

前驱查找使用 <= target：会跨过目标值，最终候选不再是第一个目标节点。

先让前驱指向新节点，再读取旧后继：旧链接已经被覆盖，新节点可能指向自己，必须先保存到新节点的后继中。

新层前驱没有设为头哨兵：这些层不在原查找范围内，前驱数组相应位置仍为空，无法完成连接。

删除时按有效总层数遍历：目标节点可能没有那么高，访问其不存在的指针会越界；更高层同值节点也不能一起删除。

把相同值当成已有元素而拒绝插入：跳表允许重复，每次插入都应增加一个节点。

最高层为空却不收缩：会保留无意义的搜索层；收缩时仍应保留底层，便于空表继续插入。

把随机平衡当成严格最坏保证：期望复杂度来自层高分布，并不保证每一次操作都是对数时间。

相似题目

题目	难度	关联与区别
707. 设计链表	中等	在有序链表上增加多层随机索引可加速查找，底层插入删除仍依赖节点连接维护。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/29278854

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！