0% completed
Problem Statement
Given the head node of a singly linked list, modify the list such that any node that has a node with a greater value to its right gets removed. The function should return the head of the modified list.
Examples:
-
Input: 5 -> 3 -> 7 -> 4 -> 2 -> 1
Output: 7 -> 4 -> 2 -> 1
Explanation: 5 and 3 are removed as they have nodes with larger values to their right. -
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 5
Explanation: 1, 2, 3, and 4 are removed as they have nodes with larger values to their right. -
Input: 5 -> 4 -> 3 -> 2 -> 1
Output: 5 -> 4 -> 3 -> 2 -> 1
Explanation: None of the nodes are removed as none of them have nodes with larger values to their right.
Constraints:
- The number of the nodes in the given list is in the range [1, 10<sup>5</sup>].
- 1 <= Node.val <= 10<sup>5</sup>
Solution
We can the monotonic stack strategy to keep track of the highest-valued nodes in the linked list, ensuring that any node with a higher value to its right gets removed.
Starting from the head of the list, we will traverse each node. At each node, we will check the value of the node against the node at the top of the stack. If the current node has a higher value, we will pop the top value from the stack. We will keep repeating this until we encounter a node with a higher value or the stack is empty. Then, the current node is pushed onto the stack. This process ensures that the stack only contains nodes in decreasing order from bottom to top.
Detailed Walkthrough:
-
Create an empty stack,
stack
. -
Initialize
cur
with thehead
of the linked list. -
Enter a loop that continues until
cur
becomesnull
:a. Enter an inner loop that continues as long as
cur
's value is greater than the value of the node at the top ofstack
:- Pop the top node from
stack
.
b. If
stack
is not empty, set thenext
of the node at the top ofstack
tocur
.c. Push
cur
ontostack
.d. Move
cur
to the next node in the linked list. - Pop the top node from
-
After exiting the loop, return the bottom node of
stack
as the head of the modified linked list. Ifstack
is empty, returnnull
.
Code
Here is how we can implement this algorithm:
Time and Space Complexity
The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. This is because every node is visited once while traversing the list. The inner loop may seem to increase the time complexity, but in fact, it doesn't, because each node is pushed and popped from the stack at most once, so the total operations are still proportional to n.
The space complexity is also O(n). This is due to the extra space required for the stack. In the worst-case scenario (when the list is sorted in ascending order), all the nodes will be pushed onto the stack, requiring n space.
Therefore, we say the algorithm is linear in both time and space complexity.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible