Left Short

PROBLEM STATEMENT

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.

Input Format

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.

Output Format:

Print the modified linked list. The elements of the modified list should be single-space separated, terminated by -1.

Note:

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints:

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

Approach 1

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.

Try Problem

Approach 2

The main idea behind this approach is that it would be easier to start deleting the required nodes from the right as we need to check the left adjacent node for each node in the given linked list. This can be done by reversing the linked list.

Reverse the given linked list.
After reversing the list, we traverse the list while checking if the next node is greater than the current node. Two situations arise :
- If it is greater, we delete the current node and move to the next node.
- If it is not greater, we simply move to the next node.

3. After iterating through the entire list, we reverse the linked list again to get the final modified list.

Try Problem