Remove Nodes From Linked List
Problem
You are given the head of a singly linked list. Delete every node that has a strictly greater value somewhere to its right, and return the head of what remains. The list holds up to 10⁵ nodes with values between 1 and 10⁵.
head = 5 → 2 → 13 → 3 → 813 → 8def remove_nodes(head):
stack = []
node = head
while node:
while stack and stack[-1].val < node.val:
stack.pop()
stack.append(node)
node = node.next
for i in range(len(stack) - 1):
stack[i].next = stack[i + 1]
stack[-1].next = None
return stack[0]function removeNodes(head) {
const stack = [];
for (let node = head; node; node = node.next) {
while (stack.length && stack[stack.length - 1].val < node.val) {
stack.pop();
}
stack.push(node);
}
for (let i = 0; i + 1 < stack.length; i++) {
stack[i].next = stack[i + 1];
}
stack[stack.length - 1].next = null;
return stack[0];
}ListNode removeNodes(ListNode head) {
Deque<ListNode> stack = new ArrayDeque<>();
for (ListNode node = head; node != null; node = node.next) {
while (!stack.isEmpty() && stack.peek().val < node.val) {
stack.pop();
}
stack.push(node);
}
ListNode next = null;
while (!stack.isEmpty()) {
ListNode cur = stack.pop();
cur.next = next;
next = cur;
}
return next;
}ListNode* removeNodes(ListNode* head) {
vector<ListNode*> stack;
for (ListNode* node = head; node; node = node->next) {
while (!stack.empty() && stack.back()->val < node->val) {
stack.pop_back();
}
stack.push_back(node);
}
for (int i = 0; i + 1 < (int)stack.size(); i++) {
stack[i]->next = stack[i + 1];
}
stack.back()->next = nullptr;
return stack[0];
}Explanation
A node survives exactly when no value to its right is greater than it. That means the survivors are the suffix maxima of the list — reading left to right, they form a non-increasing sequence. Any structure that maintains "a non-increasing sequence of values seen so far" is a job for a monotonic stack.
Scan the list once. Before pushing the current node, pop every stack node whose value is strictly smaller than the current value: the current node sits to their right and is greater, so those popped nodes are precisely the ones the problem says to delete. Then push the current node — it might still survive, depending on what comes later.
Because every push keeps the stack non-increasing from bottom to top, when the scan ends the stack holds exactly the surviving nodes in their original order. One final pass links them together — stack[i].next = stack[i + 1], with the top's next set to null — and the bottom of the stack is the new head.
On the default example 5 → 2 → 13 → 3 → 8: push 5, push 2 (2 ≤ 5). Then 13 arrives and pops 2 and 5 — both have 13 to their right — before being pushed. 3 is pushed (3 ≤ 13), then 8 arrives and pops 3. The stack ends as [13, 8], so the answer is 13 → 8.
Each node is pushed once and popped at most once, so the scan is O(n) time even though a single step may pop many nodes; the stack needs O(n) extra space in the worst case (a non-increasing list keeps everything). An O(1)-space alternative reverses the list, keeps a running maximum while deleting smaller nodes, and reverses back — same idea viewed from the right end.