Remove Nodes From Linked List

Medium · Stack · Explanation and code example

Reverse Twice

How it works

Finding the maximum to the right is hard when traversing left to right, but finding the maximum to the left is easy. By reversing the list first, the problem transforms: now we just need to keep nodes that are greater than or equal to all previous nodes. We traverse once while tracking the running maximum and remove smaller nodes. Finally, we reverse again to restore the original order.

Steps

  1. Reverse the linked list.
  2. Traverse the reversed list, tracking the maximum value seen so far (cur_max):
    • If cur.next.val < cur_max, skip it by setting cur.next = cur.next.next.
    • Otherwise, update cur_max and move to the next node.
  3. Reverse the list again to restore original order.
  4. Return the new head.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) extra space.

Things to watch for

Comparing with Immediate Neighbor Instead of Maximum

The problem requires removing nodes that have any larger value to their right, not just an immediately adjacent larger value. A node should be kept only if it is greater than or equal to all nodes to its right. Using the wrong comparison leads to incorrect removals.

Incorrect Stack Maintenance

When using a monotonic stack, the stack must remain strictly decreasing. Forgetting to pop smaller elements before pushing, or using the wrong comparison operator (e.g., >= instead of >), breaks the invariant and produces wrong results.

Losing the New Head After Reversal

In the reverse-twice approach, both reversals change which node is the head. Failing to capture and return the correct head after the second reversal causes the function to return a pointer into the middle of the list or a stale reference.

Python code example

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(head):
            prev, cur = None, head
            while cur:
                tmp = cur.next
                cur.next = prev
                prev, cur = cur, tmp
            return prev

        head = reverse(head)
        cur = head
        cur_max = head.val

        while cur and cur.next:
            if cur.next.val < cur_max:
                cur.next = cur.next.next
            else:
                cur_max = cur.next.val
                cur = cur.next

        return reverse(head)

C++ code example

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }

    ListNode* removeNodes(ListNode* head) {
        head = reverse(head);
        ListNode* cur = head;
        int cur_max = head->val;

        while (cur && cur->next) {
            if (cur->next->val < cur_max) {
                cur->next = cur->next->next;
            } else {
                cur_max = cur->next->val;
                cur = cur->next;
            }
        }
        return reverse(head);
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations