#2487

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Remove Nodes From Linked List

This problem requires removing nodes from a linked list when a larger node exists to their right, testing pointer manipulation skills.

linked list stack recursion monotonic stack

Problem Statement

Given the head of a singly linked list, remove every node that has a node with a greater value anywhere to its right. Return the modified linked list with remaining nodes in their original relative order.

For example, for head = [5,2,13,3,8], nodes 5, 2, and 3 are removed because larger nodes exist after them. Return head = [13,8]. Ensure pointer adjustments maintain list connectivity without extra node allocations.

Examples

Example 1

Input: head = [5,2,13,3,8]

Output: [13,8]

The nodes that should be removed are 5, 2 and 3.

Node 13 is to the right of node 5.
Node 13 is to the right of node 2.
Node 8 is to the right of node 3.

Example 2

Input: head = [1,1,1,1]

Output: [1,1,1,1]

Every node has value 1, so no nodes are removed.

Constraints

The number of the nodes in the given list is in the range [1, 105].
1 <= Node.val <= 105

Solution Approach

Reverse Traversal or Monotonic Stack

Iterate from the end of the list using recursion or a stack. Track the maximum value seen so far, removing any node smaller than this maximum. This ensures that only nodes without a larger successor remain.

In-place Pointer Updates

Update next pointers carefully when skipping nodes. Always maintain a reference to the last kept node to prevent breaking the list. This avoids extra memory overhead while preserving the original order for remaining nodes.

Iterative Scan with Single Pass

Optionally, reverse the linked list first, then iterate and remove nodes smaller than the running max. Reverse the list again to restore original order. This converts the problem into a straightforward linear scan while keeping O(1) extra space.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each node is visited at most twice during traversal or stack operations. Space complexity is O(1) if pointers are updated in-place, or O(n) if using recursion or a stack to track nodes.

What Interviewers Usually Probe

Focus on efficient pointer manipulation rather than creating new lists.
Consider reversing the list or using a monotonic stack to simplify removal logic.
Ensure consecutive nodes that need removal do not break list connectivity.

Common Pitfalls or Variants

Common pitfalls

Failing to update next pointers correctly when multiple nodes are removed consecutively.
Using nested loops leading to O(n^2) time instead of linear traversal.
Not handling edge cases where the largest node is at the end or all nodes are equal.

Follow-up variants

Return the modified list without using any extra space beyond pointers.
Remove nodes that have a greater value immediately next instead of anywhere to the right.
Apply the same removal logic on a doubly linked list, adjusting both prev and next pointers.

FAQ

What is the main pattern for Remove Nodes From Linked List?

The core pattern is linked-list pointer manipulation combined with maintaining a running maximum to remove nodes with greater values on the right.

Can I solve this without reversing the linked list?

Yes, using recursion or a monotonic stack allows traversal from end to start logically, avoiding explicit reversal.

What if all nodes have the same value?

No nodes are removed since there is no node strictly greater than any other, so the original list remains unchanged.

Is extra space required for a stack solution?

Yes, a stack can use O(n) space, but in-place reversal and pointer updates can achieve O(1) extra space.

How do I handle consecutive nodes that must be removed?

Always maintain a reference to the last kept node and update next pointers appropriately to skip all smaller consecutive nodes.

terminal

Solution

Solution 1: Monotonic Stack Simulation

We can first store the node values of the linked list into an array $nums$. Then, we traverse the array $nums$, maintaining a stack $stk$ that is monotonically decreasing from the bottom to the top. If the current element is larger than the top element of the stack, we pop the top element of the stack until the current element is less than or equal to the top element, and then we push the current element into the stack.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# 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]:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        stk = []
        for v in nums:
            while stk and stk[-1] < v:
                stk.pop()
            stk.append(v)
        dummy = ListNode()
        head = dummy
        for v in stk:
            head.next = ListNode(v)
            head = head.next
        return dummy.next

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# 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]:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        stk = []
        for v in nums:
            while stk and stk[-1] < v:
                stk.pop()
            stk.append(v)
        dummy = ListNode()
        head = dummy
        for v in stk:
            head.next = ListNode(v)
            head = head.next
        return dummy.next

Continue Practicing

#2289 steps to make array non decreasing #2454 next greater element iv #2617 minimum number of visited cells in a grid