Merge Two Sorted Linked Lists

You are given two sorted linked lists. Your task is to merge these two lists and produce a new sorted list that contains all the elements from the original lists.

The two input lists are in non-decreasing order. Formally, if the lists are represented as sequences \(L_1 = [a_1, a_2, \dots, a_n]\) and \(L_2 = [b_1, b_2, \dots, b_m]\), you need to output the merged list \(L = [c_1, c_2, \dots, c_{n+m}]\) such that:

\(c_1 \le c_2 \le \cdots \le c_{n+m}\)

Note: Even if one or both lists are empty, your program should handle these cases appropriately.

inputFormat

The first line contains two non-negative integers n and m separated by a space, representing the number of elements in the first and second linked lists respectively. The second line contains n integers in sorted order (if n > 0), and the third line contains m integers in sorted order (if m > 0).

If one of the lists is empty, its corresponding line will be empty.

outputFormat

Output the merged sorted list as a sequence of integers separated by a single space. If both lists are empty, output an empty line.

3 3
1 2 4
1 3 4

1 1 2 3 4 4