Sponsored
Sponsored
This approach involves reversing the linked list and using a stack to maintain the maximum values encountered so far. This allows us to easily determine which nodes have a greater value to their right.
Time Complexity: O(n), where n is the number of nodes in the linked list since each node is processed twice.
Space Complexity: O(n), due to the use of an additional stack to store nodes.
1class ListNode {
2 int val;
3 ListNode next;
4 ListNode() {}
5 ListNode(int val) { this.val = val; }
6 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7}
8
9class Solution {
10 public ListNode removeNodes(ListNode head) {
11 Stack<ListNode> stack = new Stack<>();
12 ListNode current = head;
13
14 // Traverse the list and use the stack to maintain the valid nodes.
15 while (current != null) {
16 while (!stack.isEmpty() && stack.peek().val < current.val) {
17 stack.pop();
18 }
19 stack.push(current);
20 current = current.next;
21 }
22
23 // Reconstruct the modified list
24 ListNode dummy = new ListNode(0);
25 ListNode last = dummy;
26 while (!stack.isEmpty()) {
27 last.next = new ListNode(stack.pop().val);
28 last = last.next;
29 }
30
31 return dummy.next;
32 }
33}This Java solution reverses the traversal order using a stack. It similarly rebuilds the list with qualifying nodes by popping and pushing nodes onto a stack before reconstructing the modified list.
This approach uses recursion to traverse the list and solve the problem recursively by backtracking from the end of the list to the start.
Time Complexity: O(n) - as each node is visited exactly once.
Space Complexity: O(n) - due to recursive stack space used during function calls.
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
if (!head || !head->next) return head;
head->next = removeNodes(head->next);
return (head->next && head->val < head->next->val) ? head->next : head;
}
};The recursive solution traverses to the end of the list, then checks if the current node should be part of the result or skipped based on the value comparison of its next node, ensuring that nodes with greater values are prioritized.