You are given a Singly Linked List of integers. Modify the linked list by removing the nodes from the list that have a greater valued node on their adjacent left in the given linked list.
The first line of the input contains 'L' space-separated integers denoting the elements of the singly linked list terminated by -1. Hence, -1 would never be a list element.
Print the modified linked list. The elements of the modified list should be single-space separated, terminated by -1.
You don’t need to print anything; It has already been taken care of. Just implement the given function.
0 <= L <= 5 * 10^5 -10^9 <= node.data <= 10^9 and data != -1 Where 'L' is the number of nodes in the Linked-List. Time Limit : 1 sec
We use a variable ‘DELETED_VALUE’ to keep track of the value of the last node deleted. This variable is initialized with the value -1 as -1 can never be a list element.
If ‘DELETED_VALUE’ is not equal to -1, this means that we have just deleted a node and we need to compare the value of the next node with ‘DELETED_VALUE’. We iterate through the linked list checking if the value of the next node is less than the value of the current node. Thus, the following situations arise :
- The value of the next node is less than the value of the current node and ‘DELETED_VALUE’ = -1 : Set ‘DELETED_VALUE’ to the value of the next node and delete the next node.
- ‘DELETED_VALUE’ != -1 and value of the next node is less than ‘DELETED_VALUE’ : Set deletedValue to the value of the next node and delete the next node.
- In all the other cases, set ‘DELETED_VALUE’ to -1 and move to the next node.