Practice: Sorted Union

Problem statement

The input consists of two lists in sorted order, and we must construct a new list to represent the reunion of the two lists. The reunion must maintain the sorted order. The two input lists must remain unchanged.

We can only traverse each list at most once. That is, the complexity should be $O(n)$ ...