Merge Two Sorted Linked Lists

You are given two sorted linked lists. Your task is to merge these two lists into a single sorted linked list. In doing so, you should reuse the existing nodes and minimize the creation of new nodes. Use the classic dummy node method for simplicity.

The merging process involves comparing the head nodes of the two lists and appending the smaller one to the merged list. Continue this process until one of the lists is exhausted, and then attach the remainder of the other list.

The mathematical idea can be summarized as: [ L = \text{merge}(L_1, L_2) \quad \text{where} \quad L_1 = [a_1, a_2, \dots, a_n],; L_2 = [b_1, b_2, \dots, b_m] ]

The final merged list should be in ascending order.

inputFormat

Input is read from standard input (stdin). The first line contains an integer n, denoting the number of nodes in the first linked list. The second line contains n space-separated integers representing the values of the first list (if n = 0, this line may be empty). The third line contains an integer m, the number of nodes in the second linked list. The fourth line contains m space-separated integers representing the values of the second list.

outputFormat

Output the merged linked list as space-separated integers in one line to the standard output (stdout).## sample

3
1 2 4
3
1 3 4

1 1 2 3 4 4