Merge Two Sorted Linked Lists In-Place

You are given two sorted singly linked lists. Your task is to merge the two lists into a single sorted linked list in-place (i.e. without using extra memory for storing new nodes). Consider the following aspects:

• Each linked list is represented by a sequence of integers in ascending order.
• If one of the lists is empty, the result is simply the non-empty list.
• You are required to implement the solution with in-place merging.

The in-place merging can be conceptually thought of as reusing the pointers of the nodes to build the final list. Mathematically, if \(n_1\) and \(n_2\) are the lengths of the two lists, the overall time complexity should be \(O(n_1+n_2)\).

inputFormat

The input consists of two lines read from standard input (stdin):

• The first line contains zero or more integers separated by spaces representing the first sorted linked list.
• The second line contains zero or more integers separated by spaces representing the second sorted linked list.

If a line is empty, it represents an empty list.

outputFormat

Output a single line to standard output (stdout) containing the elements of the merged sorted linked list separated by a single space. If the merged list is empty, output nothing.

1 3 5 7
2 4 6 8

1 2 3 4 5 6 7 8