Merge Two Sorted Linked Lists

Given two sorted linked lists, your task is to merge them into a single sorted linked list. The lists are given in the form of node values with their lengths. You need to implement an algorithm that works in linear time, i.e., (O(n)) where (n) is the total number of nodes, to efficiently merge the lists.

The input lists can be empty and may include negative or positive integers. Your output should be the nodes of the merged list printed in order as space-separated integers.

inputFormat

The input is read from standard input (stdin) and consists of four lines:
1. An integer (n_1) representing the number of nodes in the first linked list.
2. (n_1) space-separated integers in non-decreasing order (if (n_1 > 0); otherwise, this line is empty).
3. An integer (n_2) representing the number of nodes in the second linked list.
4. (n_2) space-separated integers in non-decreasing order (if (n_2 > 0); otherwise, this line is empty).

outputFormat

Output the merged sorted linked list as a single line of space-separated integers to standard output (stdout). If the merged list is empty, output an empty line.## sample

0

0