Smart Linked List
Last Updated: 2 Dec, 2020
Difficulty: Easy
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
Approach 1
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.
Approach 2
The idea is to keep track of the max valued node as we go through the linked list recursively.
We will create a recursive function 'SMART_LIST_HELPER' that takes two arguments, the head of the linked list and a pointer to an integer 'MAX_VALUE'. Initially, 'MAX_VALUE' is pointing to -1000 as it is the minimum value a node can acquire.
Algorithm for the 'SMART_LIST_HELPER':
- If the node does not exist, simply return ‘NULL’.
- Else,
- Recursively call the function for the next node.
- Remove the node if it’s value is less than the 'MAX_VALUE' because there exists a node of greater value in its right side.
- Now, compare the value of node and 'MAX_VALUE',
- If the value of the node is greater than the 'MAX_VALUE', 'MAX_VALUE' will be the value of the node.
- Return the head node of the linked list.
The final returned linked list will be a smart linked list.
Approach 3
Algorithm:
- Reverse the given linked list.
- Initialize an integer ‘MAX_VALUE’ to the value of the head node.
- Initialize a pointer ‘CURRENT’ pointing to the head node.
- Traverse the reversed linked list.
- If the value of the current’s next node is smaller than the ‘MAX_VALUE’, remove the current’s next node.
- Else if the value of the current’s next node is greater than the ‘MAX_VALUE’, move the current node to its next node and update the ‘MAX_VALUE’ by the value of the current node.
- Reverse the linked list again to obtain the original order.
- After the above process, return the modified linked list as it will be a smart linked list.
SIMILAR PROBLEMS
Mario And His Princess
Posted: 12 May, 2022
Difficulty: Moderate
LRU Cache
Posted: 10 Sep, 2022
Difficulty: Moderate
8-Queen Problem
Posted: 19 Dec, 2022
Difficulty: Easy
Delete Nodes On Regular Intervals
Posted: 19 Dec, 2022
Difficulty: Ninja
Add One To Linked List
Posted: 19 Dec, 2022
Difficulty: Hard
