Sort Biotonic DLL

Moderate

0/80

Average time to solve is 10m

Contributed by

7 upvotes

Asked in company

Problem statement

Sort the given biotonic doubly linked list.

Note :

Biotonic Doubly linked list is the one which is first increasing and then decreasing. A strictly increasing or strictly decreasing doubly linked list is also biotonic.

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

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

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

Output Format :

For each test case, print the sorted doubly linked list.

The output of each test case is printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 5 * 10^4
-10^9 <= data <= 10^9 and data != -1
Where T is the number of test cases, N is the length of the doubly linked list.

Time Limit : 1sec

Sample Input 1:

3
1 5 8 4 2 -1
9 10 -1
4 3 -1

Sample Output 1:

1 2 4 5 8 -1
9 10 -1
3 4 -1

Explanation for Sample Input 1:

For first test case : 
On sorting the doubly linked list, we get
1 2 4 5 8

Sample Input 2:

2
1 4 4 3 2 -1
5
1 1 1 1 1 -1

Sample Output 2:

1 2 3 4 4 -1
1 1 1 1 1 -1

Hint 1

Hint 2

Hint 3

Think of the same way you would sort an array using MergeSort, but for the linked list, we will change pointers rather than swapping data.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Sorting Approach

The main idea is to store the values of all nodes in a list and then sort that list. After that create a doubly-linked list of N size where N is the size of the list and the value of ith node from left is ith value in a list from i equal to 1 to N.

Time Complexity

O(N*log(N)) where N is the total number of nodes in the doubly linked list.

We are sorting an array containing values of all nodes. Hence time complexity is O(N*log(N)).

Space Complexity

O(N) where N is the total number of nodes in the doubly linked list.

We are creating a list of N size. Hence space complexity is O(N).

(100% EXP penalty)

Sort Biotonic DLL

Console