Merge Two Sorted Lists (In-Place) Problem Statement

You are given two sorted linked lists. Your task is to merge them to form a combined sorted linked list and return the head of this final linked list.

Example:

Input:

First list: 1 -> 4 -> 5 -> NULL
Second list: 2 -> 3 -> 5 -> NULL

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 5 -> NULL

Explanation:

The nodes from both input lists are merged into a single sorted linked list.

Constraints:

• 1 <= T <= 10
• 1 <= L <= 10⁵
• 1 ≤ data ≤ 10⁶ and data ≠ -1

Input:

The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Each test case consists of:

The first line contains the elements of the first linked list, separated by spaces, and terminated by -1.

The second line contains the elements of the second linked list, separated by spaces, and terminated by -1.

Output:

For each test case, print the merged final linked list. The elements of the list must be separated by a single space and terminated by -1.

Note:

You do not need to print the result yourself; implement the function returning the head of the merged list.

Follow-up:

Try to solve this problem in linear time complexity and constant space complexity.