4

Smart Linked List

Difficulty: EASY
Contributed By
Ambuj verma
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

You are given a Singly Linked List of integers. The linked list is called a smart linked list if no node in the list has a greater valued node on its right side. Convert the given linked list into a smart linked list.

A singly linked list is a type of linked list that is unidirectional; that is, it can be traversed in only one direction from head to the last node (tail).
Note :
If the given linked list is already a smart linked list, you don’t have to do anything.
Input Format
The first line of input contains an integer T, the number of test cases.

The first and the only line of every test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
Output Format:
For every test case, return the modified linked list. The elements of the modified list should be single-space separated, terminated by -1.
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^3 <= data <= 10^3 and data != -1

Time Limit: 1 sec
Sample Input 1:
1 
6 10 7 8 5 -1
Sample Output 1:
10 8 5 -1 
Explanation of sample input 1:
The given linked list is not a smart linked list. We can see that there are two nodes, 6 and 7 which have a greater valued node to their right ( Node with value 6 has nodes with values 10, 7 and 8 and node with value 7 has a node with value 8 on the right side respectively ). So, we will remove these nodes in order to make the linked list smart. 
The modified linked list after the above process is 10 8 5 -1.
Sample Input 2:
3
5 10 -6 4 7 -1
10 20 30 40 50 -1
-10 -20 -30 -40 -50 -1 
Sample Output 2:
10 7 -1
50 -1
-10 -20 -30 -40 -50 -1
Reset Code
Full screen
copy-code
Console