Merge Two Sorted Linked Lists

You are given two sorted singly linked lists. Your task is to merge these two lists into a single sorted linked list. The merging process should splice together the nodes of the two lists without creating new nodes, maintaining the original order.

Details: The linked lists are represented as sequences of integers in non-decreasing order. If an input line is empty, it represents an empty list. You must merge the two lists and output the merged list in sorted order.

Constraints:
The number of nodes in each list is in the range \([0, 50]\).
Each node's value satisfies \(-100 \leq \text{Node.val} \leq 100\).
Both linked lists are already sorted in non-decreasing order.

Note: Use the following merging algorithm: \[ \text{Let } l1 \text{ and } l2 \text{ be the two input lists. Create a dummy node and use a pointer } tail \text{ to build the merged list. While both } l1 \text{ and } l2 \text{ are non-empty, choose the smaller node, attach it to } tail, \text{ and move forward. Append any remaining nodes afterwards.} \]

inputFormat

The input consists of two lines read from standard input (stdin). The first line contains the values of the first linked list separated by spaces, and the second line contains the values of the second linked list separated by spaces. If a line is empty, the corresponding linked list is empty.

outputFormat

Output the merged sorted linked list as a sequence of integers separated by spaces to standard output (stdout). If the merged list is empty, output nothing.## sample