= Solution
Check that at least one real node exists, then compose the two helpers:
``
def deleteMin(): Int = {
require(bagHeader.next != null, "bag is empty")
val smallest = findMin(bagHeader.next)
val answer = smallest.datum
delete(smallest)
answer
}
``
The <precondition> check makes `findMin` applicable. Its result belongs to the real-node <sequence>, satisfying `delete`'s <precondition>. Consequently \b[one minimum value is returned and exactly one occurrence is removed]; duplicates remain as distinct nodes. Saving the datum before deletion also separates the return value from subsequent link mutation. Two linear traversals still give $O(m)$ time for a <multiset> containing $m$ nodes, with constant auxiliary space.
Back to article page
