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.
How many times is a tree node visited in a depth first search?
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
vor the stack is empty. This ensures thatvis the greatest element thus far and will be included in the final list. - After ensuring that
stkonly contains elements greater or equal tov, we appendvtostk.
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.
Which two pointer techniques do you use to check if a string is a palindrome?
Example 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. Sincestkis empty, we add5tostk. - Move to
4, compare with the top element ofstk(which is5). Since4is 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
381/**
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}
581// 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};
471// 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}
50Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Time 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
numslist isO(n)wherenis 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
numslist holds all the values from the linked list at once, which requiresO(n)space. - The
stkstack 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.
Which of the following array represent a max heap?
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
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.