Two lists are each sorted in non-decreasing order. Merge them into one sorted list. In an interview this is usually asked with linked lists; here the lists come as numbers on stdin, but treat them as lists you may only walk forward.
Constraints
- 0 ≤ n, m ≤ 100000
Input and output
- Input
- Line 1: n, then n integers Line 2: m, then m integers
- Output
- The merged values separated by single spaces (an empty line if both lists are empty).
Examples
Input 1
3 1 4 6
2 2 5Output
1 2 4 5 6Interleaved.
Input 2
0
3 1 2 3Output
1 2 3First list empty.
Show hints
- Compare the two heads; the smaller one goes next.
Show the explanation
Keep one pointer into each list. Repeatedly take the smaller head and advance that pointer; when one list runs out, append the rest of the other. With real linked lists you relink the existing nodes using a dummy head, so no new nodes are allocated. O(n + m) time, O(1) extra space for the linked version.
Original UniCircle question. Last reviewed 21 Oct 2026.