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.
1function ListNode(val, next) {
2 this
The JavaScript implementation employs recursion to traverse the linked list and decide post-traversal which nodes should be retained by safely backtracking to the start, verifying each node’s validity.