Merge Two Sorted Linked Lists

You are given two sorted linked lists. Your task is to merge these two lists into one new sorted linked list by splicing together the nodes of the original lists. The expected time complexity is \(O(n+m)\), where \(n\) and \(m\) are the number of nodes in the first and second list, respectively.

The input is provided via standard input, and the merged list must be output to standard output. Note that the lists are represented as sequences of integers.

inputFormat

The input consists of four lines:

• The first line contains an integer \(n\), the number of elements in the first sorted list.
• The second line contains \(n\) space-separated integers in non-decreasing order. If \(n=0\), this line will be empty.
• The third line contains an integer \(m\), the number of elements in the second sorted list.
• The fourth line contains \(m\) space-separated integers in non-decreasing order. If \(m=0\), this line will be empty.

outputFormat

Output a single line containing the merged sorted list. The numbers should be space-separated. If both lists are empty, output an empty line.

3
1 3 5
3
2 4 6

1 2 3 4 5 6