Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Smart Linked List

Easy
0/40
Average time to solve is 15m
profile
Contributed by
7 upvotes
Asked in company
Intuit

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Full screen
Console