2487. Remove Nodes From Linked List
Problem Description
In this problem, we are working with a singly linked list, where each node has an integer value. Our task is to modify the linked list by removing all nodes that are followed by nodes with greater values. To put it in another way, for every node in the linked list, if there exists a node to its right (i.e., further along the linked list) with a larger value, we must remove that node. The final linked list should only consist of nodes that do not have any higher valued nodes to their right. We are required to return the head of the modified linked list after performing the deletions.
Intuition
The intuition behind the solution is to process the nodes of the original linked list not from the beginning to the end but in reverse order. When traversing the list from right to left, we can keep track of the maximum value seen so far, and only keep nodes with values greater than this maximum. This way, we ensure that all remaining nodes do not have any nodes with greater values to their right by the definition of our traversal.
To implement this, we first convert the linked list to an array (nums
), allowing us to access elements in reverse order. Then we use a stack (stk
) to help us identify the nodes to keep. When traversing the array in reverse, we compare the current nodeās value with the top element of the stack (if the stack is not empty). If the current node's value is larger, we pop elements from the stack until we find a larger value or the stack becomes empty. This enforces that all elements left in the stack do not have greater values to their right. After that, we add the current value to the stack.
Ultimately, we use the values in the stack to rebuild the linked list from left to right. The stack itself now acts as a blueprint for our final modified linked list, preserving the order of the nodes that have been kept. We start with an empty sentinel node (dummy
) and then append all nodes from the stack to this sentinel node. Finally, we return the next
node of the sentinel node, which represents the head of our modified list.
Learn more about Stack, Recursion, Linked List and Monotonic Stack patterns.
Solution Approach
The solution follows a two-step approach: transforming the linked list into an array and then processing that array using a stack to build our final linked list.
Firstly, we initialize an empty array named nums
. We then iterate over the linked list starting from the head
and append each node value to the nums
array. This conversion allows easier manipulation of nodes in reverse order, which is essential for solving the problem.
Next, we use a stack to keep track of the nodes that will remain in the linked list after removal of the others. Starting with an empty list named stk
, we iterate over the nums
array. For each value v
, we perform the following steps:
- We check if the stack is not empty and the top element is less than
v
. - If so, we continuously pop elements from the stack until we find an element greater than
v
or the stack is empty. This ensures thatv
is the greatest element thus far and will be included in the final list. - After ensuring that
stk
only contains elements greater or equal tov
, we appendv
tostk
.
By this process, we effectively reverse the nums
array and filter out values such that no element has a greater value following it.
After processing the entire nums
array in this way, stk
contains all the values that should appear in the modified linked list, in reverse order. To turn this stack into a linked list, we create a dummy head node dummy
to serve as a non-value holding starting point. We then iterate over the stk
array, and for each value v
, we append a new node with value v
to the end of the list starting at the dummy
node.
Thus, we are able to create the new linked list with all nodes not followed by a node with greater valueāto the rightāall in one pass through the stk
. The final step is to return dummy.next
, which points to the head of our new modified linked list.
The overall process utilizes a conversion to array for ease of traversal, a stack for filtering necessary nodes, and a re-conversion to linked list. This approach is efficient since it traverses the list of nodes only twice, regardless of the number of removals necessary.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach. Consider the following singly linked list:
1 -> 2 -> 3 -> 4 -> 5
According to the problem statement, we want to keep only the nodes that do not have a higher valued node to their right. In this case, since the list is ordered in ascending fashion, all nodes but the last one would be removed, leaving us with:
5
Let's apply the solution approach step by step.
Converting Linked List to Array
First, we initialize an empty array nums
and iterate from the head to the end of the linked list, appending each node's value to nums
.
After this step, nums
will be: [1, 2, 3, 4, 5]
.
Processing the Array Using a Stack
We initialize a stack stk
and iterate over nums
in reverse order (from right to left):
- Start with
5
. Sincestk
is empty, we add5
tostk
. - Move to
4
, compare with the top element ofstk
(which is5
). Since4
is less than5
, we discard4
. - The same logic applies to
3
,2
, and1
. Since all are less than the top element5
, they are all discarded.
After this process, stk
contains just [5]
.
Rebuilding the Linked List
Now, we create a sentinel node dummy
and start creating new linked list nodes using the values in stk
.
Since stk
has one element, 5
, we create a node with the value 5
and link it to the dummy
.
Finally, we return dummy.next
which points to the head of the modified list.
The modified list will be a single node with the value:
5
Thus, our example list has been modified in place to remove all nodes that have a larger valued node to their right, leaving us with the correct result according to the problem description.
Solution Implementation
1# Definition for singly-linked list.
2class ListNode:
3 def __init__(self, val=0, next=None):
4 self.val = val
5 self.next = next
6
7class Solution:
8 def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
9 # List to store the values of the linked list nodes
10 node_values = []
11
12 # Traverse the linked list and store the values in node_values list
13 while head:
14 node_values.append(head.val)
15 head = head.next
16
17 # Stack to maintain the required condition and store the final values
18 stack = []
19 for value in node_values:
20 # If the current value is greater than the last value in the stack,
21 # pop the last value to ensure monotonically increasing order
22 while stack and stack[-1] < value:
23 stack.pop()
24 # Append the current value to the stack
25 stack.append(value)
26
27 # Create a dummy node to serve as a starting point for the new linked list
28 dummy = ListNode()
29 current = dummy
30
31 # Convert the stack to a linked list
32 for value in stack:
33 current.next = ListNode(value)
34 current = current.next
35
36 # Return the head of the newly formed linked list
37 return dummy.next
38
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5 int val;
6 ListNode next;
7
8 ListNode() {}
9
10 ListNode(int val) {
11 this.val = val;
12 }
13
14 ListNode(int val, ListNode next) {
15 this.val = val;
16 this.next = next;
17 }
18}
19
20class Solution {
21 // Function to remove nodes from the linked list that have a value greater to the right
22 public ListNode removeNodes(ListNode head) {
23 // Initialize an array to store the node values
24 List<Integer> nodeValues = new ArrayList<>();
25
26 // Iterate through linked list to collect values
27 while (head != null) {
28 nodeValues.add(head.val);
29 head = head.next;
30 }
31
32 // Use a stack to keep track of nodes to be preserved
33 Deque<Integer> stack = new ArrayDeque<>();
34 for (int value : nodeValues) {
35 // Remove all elements from stack that are smaller than current value
36 while (!stack.isEmpty() && stack.peek() < value) {
37 stack.pop();
38 }
39 // Push the current value onto the stack
40 stack.push(value);
41 }
42
43 // Create a dummy node to build the resulting linked list
44 ListNode dummy = new ListNode(0);
45 ListNode current = dummy;
46
47 // Build the new linked list by popping values from the stack
48 while (!stack.isEmpty()) {
49 // Since stack is LIFO, use stack.pollLast() to maintain original order of remaining nodes
50 current.next = new ListNode(stack.pollLast());
51 current = current.next;
52 }
53
54 // Return the next node of dummy since first node is a placeholder
55 return dummy.next;
56 }
57}
58
1// Definition for singly-linked list.
2struct ListNode {
3 int val;
4 ListNode *next;
5 ListNode() : val(0), next(nullptr) {} // Default constructor
6 ListNode(int x) : val(x), next(nullptr) {} // Constructor with value parameter
7 ListNode(int x, ListNode *next) : val(x), next(next) {} // Constructor with value and next node parameters
8};
9
10class Solution {
11public:
12 ListNode* removeNodes(ListNode* head) {
13 vector<int> values; // This will hold the values of the nodes of the linked list
14
15 // Traverse the linked list and fill the vector with node values
16 while (head) {
17 values.emplace_back(head->val);
18 head = head->next;
19 }
20
21 vector<int> stack; // This is used to keep track of the nodes to keep
22
23 // Iterate over the values and use the stack to filter the values
24 for (int value : values) {
25 // If the last value in the stack is less than the current value, pop from stack
26 while (!stack.empty() && stack.back() < value) {
27 stack.pop_back();
28 }
29 // Push the current value onto the stack
30 stack.push_back(value);
31 }
32
33 // Create a dummy node to build the new linked list
34 ListNode* dummy_head = new ListNode();
35 ListNode* current = dummy_head; // Pointer to iterate through the new list
36
37 // Construct the new linked list from the stack values
38 for (int value : stack) {
39 current->next = new ListNode(value);
40 current = current->next;
41 }
42
43 // Return the head of the new linked list, which is after the dummy node
44 return dummy_head->next;
45 }
46};
47
1// Definition for singly-linked list.
2class ListNode {
3 val: number;
4 next: ListNode | null;
5
6 constructor(val: number = 0, next: ListNode | null = null) {
7 this.val = val;
8 this.next = next;
9 }
10}
11
12// Function to remove nodes according to the specific criteria described in the original C++ function.
13function removeNodes(head: ListNode | null): ListNode | null {
14 // This array will hold the values of the nodes of the linked list.
15 const values: number[] = [];
16
17 // Traverse the linked list and fill the array with node values.
18 while (head) {
19 values.push(head.val);
20 head = head.next;
21 }
22
23 // This array is used to keep track of the nodes to keep.
24 const stack: number[] = [];
25
26 // Iterate over the values and use the stack to filter the values.
27 for (let value of values) {
28 // If the last value in the stack is less than the current value, pop from stack.
29 while (stack.length > 0 && stack[stack.length - 1] < value) {
30 stack.pop();
31 }
32 // Push the current value onto the stack.
33 stack.push(value);
34 }
35
36 // Create a dummy node to build the new linked list.
37 const dummyHead: ListNode = new ListNode();
38 // Pointer to iterate through the new list.
39 let current: ListNode = dummyHead;
40
41 // Construct the new linked list from the stack values.
42 for (let value of stack) {
43 current.next = new ListNode(value);
44 current = current.next;
45 }
46
47 // Return the head of the new linked list, which is after the dummy node.
48 return dummyHead.next;
49}
50
Time and Space Complexity
Time Complexity
The time complexity of the code is determined by several loops over the input list:
- The first loop that constructs the
nums
list isO(n)
wheren
is the size of the linked list since it visits each node exactly once. - The second loop uses a while loop inside a for loop to process each element and possibly multiple elements within the stack (
stk
). In the worst case, each element is pushed and popped exactly once, which still yieldsO(n)
because each element is handled twice at most (once for pushing and once for popping). - The third loop creates the new linked list from the stack, and this is also
O(n)
since each element in the stack is visited once.
Thus, the overall time complexity is O(n) + O(n) + O(n) = O(n)
.
Space Complexity
The space complexity is determined by the additional space used by the algorithm:
- The
nums
list holds all the values from the linked list at once, which requiresO(n)
space. - The
stk
stack can potentially hold all the values (if they are sorted in increasing order), so it also requiresO(n)
space. - The new linked list that is constructed is also counted toward the space complexity, but since the original list is traversed as well, this does not contribute additional space overhead in terms of complexity analysis.
The total space complexity is O(n) + O(n) = O(n)
since the space required for the stack and the space required for the nums list are additive.
Learn more about how to find time and space complexity quickly using problem constraints.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Want a Structured Path to Master System Design Too? Donāt Miss This!