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 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def removeNodes(self, head: ListNode) -> ListNode:
8 stack = []
9 current = head
10
11 # Traverse the list in a reversed manner
12 while current:
13 while stack and stack[-1].val <= current.val:
14 stack.pop()
15 stack.append(current)
16 current = current.next
17
18 # Reconstruct the result list from the stack
19 dummy = ListNode(0)
20 last = dummy
21 for node in reversed(stack):
22 last.next = ListNode(node.val)
23 last = last.next
24 return dummy.nextThe code defines a function removeNodes that takes a singly linked list and removes nodes that have a node with a greater value to their right. It uses a stack to keep track of potential candidates for the resulting list, reconstructing the list after determining the correct elements.
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.