Merge Two Sorted Linked Lists Problem Statement

You are provided with two sorted linked lists. Your task is to merge them into a single sorted linked list and return the head of the combined linked list.

Input:

The first line indicates the integer 'T', which is the number of test cases. Each test case consists of: 
The first line contains the elements of the first linked list, separated by spaces, ending with -1.
The second line contains the elements of the second linked list, separated by spaces, ending with -1.

Output:

For each test case, output the merged linked list, with elements separated by spaces, ending with -1. Each test case's output should be on a new line.

Example:

Input:

1 4 5 -1
2 3 5 -1

Output:

1 2 3 4 5 5 -1

Constraints:

• 1 <= T <= 10
• 1 <= L <= 10^5
• 1 ≤ data ≤ 10^6 and data != -1

Note:

The provided linked lists may be empty, represented by ending immediately with -1.

Follow-up:

Attempt to solve this problem using a method with linear time complexity and without additional space usage beyond constant space complexity.