Merge Two Sorted Linked Lists

You are given two sorted singly linked lists L1 and L2. Your task is to merge these two lists into a single sorted linked list. The merging process is done by comparing the current nodes of each list and adding the smaller value to the new list. Mathematically, this can be described as: if \(L1[i] \le L2[j]\), then choose \(L1[i]\); otherwise choose \(L2[j]\).

The input is provided via standard input and the result should be printed to standard output. The merged list should have all values in non-decreasing order.

inputFormat

The input is given in three lines:

• The first line contains two integers \(n\) and \(m\), which denote the number of elements in the first and second lists respectively.
• The second line contains \(n\) integers in non-decreasing order representing the first list. If \(n = 0\), this line will be empty.
• The third line contains \(m\) integers in non-decreasing order representing the second list. If \(m = 0\), this line will be empty.

outputFormat

Output a single line containing the merged sorted list. The numbers should be separated by a single space. If the merged list is empty, output an empty line.

3 3
1 2 4
1 3 4

1 1 2 3 4 4