Build Sorted Linked List

Moderate

0/80

Contributed by

2 upvotes

Asked in companies

Problem statement

You have given two sorted linked lists 'FIRST' and 'SECOND'. Your task is to build a new sorted list which contains the elements of given two sorted linked list.

For example:

If the first list is: 1 -> 2 -> 3 -> NULL and the second list is: 2 -> 3 -> 5 -> NULL

Then new sorted linked list will be  1 -> 2 -> 2 -> 3 -> 3 -> 5 -> NULL.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

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

The first line of each test case contains the elements of the first linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

The second line of each test case contains the elements of the second linked list separated by a single space and terminated by -1.

Output Format:

For each test case, return the new sorted linked list. The elements of the linked list must be separated by a single space and terminated by -1.

Print output of each test case in a separate line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
0 <= | FIRST |, | SECOND | <= 10^5
1 ≤ DATA ≤ 10^6 and DATA != -1

Time Limit: 1 sec

Follow-up:

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

Sample Input 1:

Sample Output 1:

1 2 2 3 3 5 -1
1 3 4 6 7 8 -1

Explanation of Input 1:

The first test case, refer example's explanation.

The second test case, the first list is: 7 -> 8 -> NULL
The second list is: 1 -> 3 -> 4 -> 6 -> NULL
The final list would be: 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> NULL

Sample Input 2:

2
5 -1
1 3 6 10 -1
1 1 1 -1
1 1 1 -1

Sample Output 2

1 3 5 6 10 -1
1 1 1 1 1 1 -1

Approaches (1)

Approach 1

App 1

Time Complexity

Space Complexity

(100% EXP penalty)

Build Sorted Linked List

Console