2487. Remove Nodes From Linked List

MediumStackRecursionLinked ListMonotonic Stack

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 that v is the greatest element thus far and will be included in the final list.
After ensuring that stk only contains elements greater or equal to v, we append v to stk.

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 Evaluator

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. Since stk is empty, we add 5 to stk.
Move to 4, compare with the top element of stk (which is 5). Since 4 is less than 5, we discard 4.
The same logic applies to 3, 2, and 1. Since all are less than the top element 5, 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 is O(n) where n 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 yields O(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 requires O(n) space.
The stk stack can potentially hold all the values (if they are sorted in increasing order), so it also requires O(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don’t know