Remove Nodes From Linked List - Practice Coding Problems

Remove Nodes From Linked List - Problem

You are given the head of a linked list. Your task is to remove every node that has a node with a strictly greater value anywhere to the right side of it.

Think of it this way: a node survives if it's the maximum among all nodes from its position to the end of the list. All other nodes should be eliminated!

Example: In the list [5,2,13,3,8], node 5 gets removed because 13 > 5, node 2 gets removed because 13 > 2, node 3 gets removed because 8 > 3. The result is [13,8].

Return the head of the modified linked list.

Input & Output

example_1.py — Standard Case

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

› Output: [13,8]

💡 Note: Node 5 is removed because 13 > 5. Node 2 is removed because 13 > 2. Node 3 is removed because 8 > 3. Nodes 13 and 8 have no greater values to their right, so they remain.

example_2.py — Ascending Order

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

› Output: [1,1,1,1]

💡 Note: No node has a strictly greater value to its right (all values are equal), so all nodes remain in the list.

example_3.py — Single Node

$ Input: head = [1]

› Output: [1]

💡 Note: A single node has no nodes to its right, so it always remains in the list.

Constraints

The number of nodes in the list is in the range [1, 10⁵]
1 ≤ Node.val ≤ 10⁵
Follow-up: Can you solve this in O(n) time and O(1) extra space?

Visualization

Tap to expand

Understanding the Visualization

Survey from Right

Start from the rightmost peak (node 8) - it's always visible since nothing blocks it

Check Peak 3

Peak 3 is blocked by peak 8 (8 > 3), so it becomes invisible

Discover Peak 13

Peak 13 is taller than peak 8, so it becomes visible and peak 8 remains visible behind it

Filter Remaining

Peaks 2 and 5 are both blocked by the tall peak 13, so they become invisible

Key Takeaway

🎯 Key Insight: Process from right to left using a monotonic decreasing stack. A node survives if there's no strictly greater value to its right, which we can determine efficiently by maintaining the maximum values seen so far.

Asked in

a Amazon 45 G Google 38 ⊞ Microsoft 32 f Meta 28

The optimal solution uses a monotonic stack with recursive processing from right to left. By maintaining a decreasing stack of values, we can determine in O(n) time which nodes should survive. The key insight is that a node survives if it's greater than or equal to the maximum value seen from its position to the end of the list.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Nested Traversal)	O(n²)	O(1)	For each node, scan the entire remaining list to check if there's a greater value
Monotonic Stack (Optimal)	O(n)	O(n)	Use a stack to maintain decreasing sequence while processing nodes from right to left

Brute Force (Nested Traversal) — Algorithm Steps

Start from the head of the linked list
For each node, traverse all remaining nodes to the right
If any right node has a greater value, mark current node for deletion
Remove all marked nodes while maintaining list connections
Return the new head

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Node 5

Node 5 scans right: finds 13 > 5, so mark for removal

Check Node 2

Node 2 scans right: finds 13 > 2, so mark for removal

Check Node 13

Node 13 scans right: no node > 13, so keep it

Check Node 3

Node 3 scans right: finds 8 > 3, so mark for removal

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

bool hasGreaterRight(struct ListNode* node) {
    struct ListNode* current = node->next;
    while (current) {
        if (current->val > node->val) {
            return true;
        }
        current = current->next;
    }
    return false;
}

struct ListNode* removeNodes(struct ListNode* head) {
    if (!head) return head;
    
    // Create dummy node to handle head removal
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    struct ListNode* prev = dummy;
    struct ListNode* current = head;
    
    while (current) {
        if (hasGreaterRight(current)) {
            // Remove current node
            prev->next = current->next;
            free(current);
            current = prev->next;
        } else {
            prev = current;
            current = current->next;
        }
    }
    
    struct ListNode* newHead = dummy->next;
    free(dummy);
    return newHead;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse input
    int values[100];
    int count = 0;
    char* token = strtok(line, " \n");
    while (token && count < 100) {
        values[count++] = atoi(token);
        token = strtok(NULL, " \n");
    }
    
    if (count == 0) {
        printf("[]\n");
        return 0;
    }
    
    // Build linked list
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = values[0];
    head->next = NULL;
    struct ListNode* current = head;
    
    for (int i = 1; i < count; i++) {
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current = current->next;
        current->val = values[i];
        current->next = NULL;
    }
    
    // Process
    struct ListNode* resultHead = removeNodes(head);
    
    // Output
    printf("[");
    bool first = true;
    while (resultHead) {
        if (!first) printf(",");
        printf("%d", resultHead->val);
        first = false;
        struct ListNode* temp = resultHead;
        resultHead = resultHead->next;
        free(temp);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we potentially scan all remaining nodes to the right

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few pointers for traversal, no additional data structures

✓ Linear Space

42.0K Views

Medium Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Nested Traversal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler