What is the brute force approach and complexity for Remove Nodes From Linked List?

For each node, check every node to its right for a strictly bigger value with time complexity O(N²) and space complexity O(N).

What is the optimal approach and complexity for Remove Nodes From Linked List?

Reverse, walk once keeping nodes at least as big as the running max, reverse back with optimal time complexity O(N) and space complexity O(1).

Remove Nodes From Linked List

Q: How do you identify the pattern for Remove Nodes From Linked List?

Look for key signals in the prompt: "remove nodes" indicates Some nodes must go. Relink around them, or build a new chain from the nodes that stay.; "strictly greater to its right" indicates The right side decides. Reversing the list turns the right side into the part already walked past, so a running max is enough.; "singly linked list" indicates We can't walk backwards, so we reverse the list first, then reverse the kept nodes back..

Medium·LeetCode #2487 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given the head of a linked list. Remove every node that has a strictly greater value somewhere to its right. Keep the other nodes in their original order, and return the head of what is left.

In short: a node is removed only when a bigger value sits somewhere after it. Equal values never remove each other.

Input

head, the first node of a singly linked list.

Output

The head of the list after the removals.

Example 1

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

Output: [13, 8]

5, 2 and 3 each have a bigger value to their right (13 or 8), so they go. 13 has nothing bigger after it, and 8 is the last node, so both stay.

Example 2

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

Output: [1, 1, 1, 1]

No value has a strictly bigger value to its right, so nothing is removed.

Example 3

Input: head = [3, 1, 3]

Output: [3, 3]

The 1 has a bigger 3 after it, so it goes. The first 3 stays, because the 3 after it is not strictly bigger.

Constraints

• The list has between 1 and 10^5 nodes.
• 1 ≤ Node.val ≤ 10^5

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“remove nodes”

→ Some nodes must go. Relink around them, or build a new chain from the nodes that stay.

“strictly greater to its right”

→ The right side decides. Reversing the list turns the right side into the part already walked past, so a running max is enough.

“singly linked list”

→ We can't walk backwards, so we reverse the list first, then reverse the kept nodes back.

Approach Complexity Ladder

Brute Force — scan the right side for each nodeO(N²)O(N)

For each node, check every node to its right for a strictly bigger value

Better — monotonic stack, one passO(N)O(N)

Walk left to right; a new value pops every smaller value on the stack

Optimal — reverse, keep the running max, reverse backO(N)O(1)

Reverse, walk once keeping nodes at least as big as the running max, reverse back

Brute Force Intuition

Put the nodes in an array. For each node, scan all the nodes after it. If any of them is strictly bigger, the node goes. Otherwise it stays. Then link the kept nodes in their original order.

Recognition rule for this sub-pattern:

Walk once, pointing each node back to the previous one.

Remember this · Linked List — Reversal

Trigger

Reverse whole / part / every k nodes, reorder, palindrome check, numbers stored as lists.

Think

Which piece do I reverse, and which nodes must I remember to reconnect afterwards?

Key question

Before reversing, who is the node just before the piece and who is just after?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Reversal translate into production architectures and low-level memory mechanics.

LLD Architecture