Problem

Submissions

Hints & solutions

Discuss

Smart Linked List

Easy

0/40

Average time to solve is 15m

Contributed by

7 upvotes

Asked in company

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 )

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

Hint 1

Hint 2

Hint 3

For every node, check if there exists a greater valued node on the right side.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

The idea is very simple. We will consider every node and check all the nodes to its right side. If we encounter a node with greater value in the right side of the current node, we will simply remove the current node.

Algorithm:

Traverse the linked list using two loops.
In the outer loop, pick every node of the linked list one by one.
In the inner loop, check the value of all the nodes to the right side of the picked node. If there exists a node with greater value than the picked node, remove the picked node from the linked list.
After the above process, return the modified linked list as it is now converted into a smart linked list.

Time Complexity

O(N * N), where ‘N’ is the number of nodes in the linked list.

For every node of the linked list, we are traversing all the nodes to its right side. The total operations performed will be (N * (N - 1) / 2). Thus, the final time complexity is O(N * (N - 1 ) / 2) = O(N * N).

Space Complexity

O(1).

We are not using any extra data structure. Only constant additional space is required.

(100% EXP penalty)

Smart Linked List

Console