Namaran

Code daily. Without assist.

2026-09-05

skip_search.cpp

struct Node {
    int key;
    std::vector<Node*> next;  // next[0] is the bottom level
};

bool contains(const Node* head, int key) {
}

スキップリストに key があるかを返す contains を書いてください。head はキーを持たない番兵のノードで、head->next.size() がリストの段数です。各ノードの next[lv] は、段 lv でそのノードの次にあるノードを指し、なければ nullptr です。どの段でもキーは小さい順に並んでいます。キーが1つもないリストでは false を返します。例の head はキー 1, 3, 6, 9 を持つリスト、empty はキーのない3段のリストです。

入力例 1

contains(&head, 6)

出力例 1

true

入力例 2

contains(&head, 7)

出力例 2

false

入力例 3

contains(&empty, 1)

出力例 3

false
Reference
bool contains(const Node* head, int key) {
    const Node* x = head;
    for (std::size_t lv = head->next.size(); lv-- > 0;) {
        while (x->next[lv] && x->next[lv]->key < key) x = x->next[lv];
    }
    const Node* y = x->next[0];
    return y && y->key == key;
}

一番上の段から始め、次のノードのキーが key より小さい間だけ右へ進み、進めなくなったら1段下ります。段を下りるときに x を head へ戻さないので、上の段で飛ばした区間を下の段で読み直すことはありません。最下段まで下りたとき、x は key より小さいキーを持つノードのうち最後のもの(なければ head)です。key があるなら、そのすぐ右の x->next[0] にあります。

lv-- > 0 は、符号なしの std::size_t で段を上から 0 まで数えるための書き方です。lv >= 0 を条件にすると、符号なしの値は常に 0 以上なのでループが終わりません。

掲載したのは参考実装で、唯一の正解ではありません。段を int で数えたり、再帰で1段ずつ下りたりしても構いません。