The union operation for `MultisetAsLinkedList` class
requires the merging of two ordered, linked lists
as shown in Program .
We have assumed that the smallest element contained in a multiset
is found at the head of the linked list and the largest is at the tail.

**Program:** `MultisetAsLinkedList` Class Union Operator Definition

The union operator takes two multisets
and computes a third multiset, the `result`, as follows.
The main loop of the program (lines 9-21) traverses the linked lists
of the two operands,
in each iteration appending the smallest remaining element the result.
Once one of the lists has been exhausted,
the remaining elements in the other list are simply appended to the result
(lines 22-25).
The total running time for the union operation, `operator+`,
is *O*(*m*+*n*),
where and
and `s` and `t` are the two operand multisets.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.