Remove Nodes From Linked List

Remove Nodes From Linked List

What is this problem about?

The Remove Nodes From Linked List interview question asks you to remove all nodes from a singly linked list such that there exists a node with a greater value to its right. In other words, keep a node only if no node to its right has a strictly greater value. The resulting list should be in non-increasing order of values from left to right.

Why is this asked in interviews?

This problem is asked at Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe because it elegantly combines linked list traversal with a monotonic stack. It tests whether a candidate can identify the right data structure to track "the maximum to the right" efficiently, and then reconstruct a linked list from filtered results. It also has a clean recursive solution, offering two distinct approaches to discuss.

Algorithmic pattern used

The primary pattern is a monotonic stack (non-increasing). Convert the linked list to an array of values. Use a monotonic stack to keep only values where no greater value comes after them: iterate right to left, maintaining a stack where each new value is greater than or equal to the stack top. Alternatively, reverse the list, apply a monotonic stack traversal, then reverse again. A recursive approach also works: recursively process the suffix, then include the current node only if it's ≥ the recursive result's head value.

Example explanation

List: 5 → 2 → 13 → 3 → 8

Looking from right:

• 8: no element to its right is greater → keep.
• 3: 8 > 3 → remove.
• 13: 8 < 13 → keep.
• 2: 13 > 2 → remove.
• 5: 13 > 5 → remove.

Result: 13 → 8.

Common mistakes candidates make

• Checking if any node to the right is greater (which would require O(n^2)) instead of using the monotonic stack to do it in O(n).
• Forgetting to rebuild the linked list from the filtered values after using a stack or array.
• Using a non-decreasing monotonic stack instead of non-increasing — the condition is "remove if a GREATER value exists to the right."
• Confusing the recursive approach: the recursive call returns the already-filtered suffix, so compare current node with the head of the returned list.

Interview preparation tip

For the Remove Nodes From Linked List coding problem, the monotonic stack and linked list interview pattern is the most efficient approach. Know both the iterative (stack) and recursive approaches — interviewers at Adobe and Google may ask for both. The recursive version is elegant but has O(n) stack space due to recursion depth on long lists, so be ready to discuss tradeoffs. Practice converting list problems to array-based processing when in-place manipulation is awkward.