Merge Two Sorted Linked Lists

You are given two sorted linked lists. Your task is to merge these two linked lists into one sorted linked list and output the merged list.

The linked lists are represented by their node values. Formally, if the two lists are given as:

• \(L_1 = [a_1, a_2, \dots, a_n]\)
• \(L_2 = [b_1, b_2, \dots, b_m]\)

Then you need to produce a merged sorted list \(L = [c_1, c_2, \dots, c_{n+m}]\) such that \(c_1 \le c_2 \le \cdots \le c_{n+m}\). This corresponds to the standard merge process in the merge sort algorithm.

The input and output will be provided via standard input and standard output respectively.

inputFormat

The input consists of three lines:

1. The first line contains two non-negative integers \(n\) and \(m\) representing the lengths of the first and second linked lists respectively.
2. The second line contains \(n\) integers separated by spaces representing the node values of the first linked list in sorted order. If \(n = 0\), this line will be empty.
3. The third line contains \(m\) integers separated by spaces representing the node values of the second linked list in sorted order. If \(m = 0\), this line will be empty.

outputFormat

Output the merged sorted linked list as a sequence of integers separated by a single space on one line. If the merged list is empty, output an empty line.

3 3
1 2 4
1 3 4

1 1 2 3 4 4