Merge Two Sorted Linked Lists

You are given two sorted linked lists. Your task is to merge these two lists into one sorted linked list.

The algorithm should combine the nodes from both lists such that the resulting list is still sorted in non-decreasing order. If one of the lists is empty, the result is simply the other list. In case both lists are empty, the output is empty.

Note: The merging process should mimic the typical linked list merge as described in textbooks. The conventional method uses a dummy node to simplify edge cases during the merge process.

Input Format: The input is provided via standard input (stdin). The first line contains an integer n which represents the number of elements in the first sorted linked list, followed by n space-separated integers. The second line starts with an integer m representing the number of elements in the second sorted linked list, followed by m space-separated integers.

Output Format: Print the merged linked list on a single line. The nodes' values should be separated by a single space. If the merged list is empty, output nothing.

The merging algorithm can be expressed mathematically as follows:

\(\text{merge}(L_1, L_2) = \begin{cases}\, L_2, & \text{if } L_1 \text{ is empty};\\ \; L_1, & \text{if } L_2 \text{ is empty};\\ \; \text{if } L_1[0]

inputFormat

The input consists of two lines:

• The first line starts with an integer n (the size of the first list) followed by n sorted integers.
• The second line starts with an integer m (the size of the second list) followed by m sorted integers.

For example, an input might look like:

3 1 2 4
3 1 3 4

outputFormat

Output the merged linked list in sorted order, with each value separated by a single space. For the above example, the output will be:

1 1 2 3 4 4

## sample

3 1 2 4
3 1 3 4

1 1 2 3 4 4