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. The merged list should be built by splicing together the nodes of the two given lists.

Note: The merging process should have a time complexity of \(O(n+m)\), where \(n\) and \(m\) are the lengths of the two lists respectively.

The input will be provided through standard input, and you should output the merged linked list to standard output. Each value in the merged list must be separated by a single space. If a list is empty, its size will be given as 0 and no elements will follow on that line.

inputFormat

The input consists of four lines:

1. An integer (n) representing the number of elements in the first list.
2. (n) space-separated integers in non-decreasing order representing the first linked list. (If (n = 0), this line will be empty.)
3. An integer (m) representing the number of elements in the second list.
4. (m) space-separated integers in non-decreasing order representing the second linked list. (If (m = 0), this line will be empty.)

outputFormat

Output a single line containing the values of the merged sorted linked list separated by a single space. If the merged list is empty, output an empty line.## sample

4
1 3 5 7
5
2 4 6 8 10

1 2 3 4 5 6 7 8 10