Left Short

Posted: 3 Oct, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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 :

 

  1. 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.
  2. ‘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.
  3. In all the other cases, set ‘DELETED_VALUE’ to -1 and move to the next node.
Try Problem