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段ずつ下りたりしても構いません。