= Solution
Assume `NumLevels >= 1`. Both <sentinel nodes> occur on every level; the tail ends every <linked list>.
``
val head = new Node(Int.MinValue)
val tail = new Node(Int.MaxValue)
for (level <- 0 until NumLevels) {
head.nexts(level) = tail
tail.nexts(level) = null
}
``
The empty <skip list> therefore has
$$
\boxed{\mathrm{head}\longrightarrow\mathrm{tail}\longrightarrow\mathrm{null}\quad\text{at every level}.}
$$
The forbidden data values distinguish the <sentinel nodes> from genuine entries.
Back to article page
