'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before', 'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before',
Update appNew update is available. Click here to update.
Last Updated: 3 Oct, 2020

Left Short

Easy
Asked in companies
DirectiD.E.Shaw

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

Approaches

01 Approach

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.