Remove Nodes From Linked List

Medium
2024.

Remove Nodes From Linked List

Remove Nodes From Linked List is a medium coding problem on stack, monotonic stack and recursion, asked in Amazon and Microsoft interviews.

You are given the head of a linked list. Remove every node that has a node with a strictly greater value anywhere to its right.

Return the head of the list that remains. The surviving nodes keep their original order.

Example 1

Input
head = [6,3,14,2,9,5]
Output
[14,9,5]
Explanation
6 and 3 have 14 to their right; 2 has 9 to its right. 14, 9 and 5 have nothing larger after them.

Example 2

Input
head = [4,4,4]
Output
[4,4,4]
Explanation
Equal values do not remove each other — only a strictly greater one does.

Example 3

Input
head = [1,2,3]
Output
[3]
Explanation
Each node is beaten by the one after it; only the last survives.

Constraints

  • The number of nodes in the list is in the range [1, 10^5]
  • 1 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var removeNodes = function(head) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Nodes From Linked List — Problem & Solution

Remove Nodes From Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Remove Nodes From Linked List is a medium coding problem on stack, monotonic stack and recursion, asked in Amazon and Microsoft interviews.

Problem statement

You are given the head of a linked list. Remove every node that has a node with a strictly greater value anywhere to its right.

Return the head of the list that remains. The surviving nodes keep their original order.

Example 1

Input: head = [6,3,14,2,9,5]
Output: [14,9,5]
Explanation: 6 and 3 have 14 to their right; 2 has 9 to its right. 14, 9 and 5 have nothing larger after them.

Example 2

Input: head = [4,4,4]
Output: [4,4,4]
Explanation: Equal values do not remove each other — only a strictly greater one does.

Example 3

Input: head = [1,2,3]
Output: [3]
Explanation: Each node is beaten by the one after it; only the last survives.

Constraints

  • The number of nodes in the list is in the range [1, 10^5]
  • 1 <= Node.val <= 10^5

Hints for Remove Nodes From Linked List

  1. Hint 1

    A node survives exactly when it is at least as large as every value after it — so the answer depends on suffix maxima.

  2. Hint 2

    Suffix maxima are easy if you walk the list from the back. How can you walk a singly linked list from the back?

  3. Hint 3

    Reverse the list, keep each node that is at least the largest value kept so far (dropping the rest), then reverse the result back.

How to solve Remove Nodes From Linked List

A node stays if and only if no later node is larger, i.e. its value is at least the maximum of the suffix after it. Reversing the list turns suffixes into prefixes, where a running maximum decides each node in one pass.

Approach

  1. Reverse the list. Its first node (the original last) always survives; set mx to its value.
  2. Walk the reversed list: if the next node's value is below mx, unlink it; otherwise move onto it and set mx to its value.
  3. Reverse the filtered list back and return its head.

Why it works

In the reversed list the nodes before a node are exactly the original nodes after it, and mx is the largest value among the kept ones — which equals the largest value among all of them, because a dropped node was smaller than some kept node. So a node is dropped exactly when a strictly greater value lies to its right in the original list.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Use < for dropping, not <=: equal values survive.
  • A monotonic stack (pop smaller values, push the current node) gives the same list in O(n) extra space; recursion from the tail works too but can overflow the stack on 10^5 nodes.

Reference solution

Python

from typing import Optional

def flip_list(h):
    prev = None
    while h:
        h.next, prev, h = prev, h, h.next
    return prev

def removeNodes(head: Optional[ListNode]) -> Optional[ListNode]:
    rev = flip_list(head)
    mx, cur = rev.val, rev
    while cur.next:
        if cur.next.val < mx:
            cur.next = cur.next.next
        else:
            cur = cur.next
            mx = cur.val
    return flip_list(rev)

Java

static ListNode flipList(ListNode h) {
    ListNode prev = null;
    while (h != null) { ListNode nx = h.next; h.next = prev; prev = h; h = nx; }
    return prev;
}

public static ListNode removeNodes(ListNode head) {
    ListNode rev = flipList(head), cur = rev;
    int mx = rev.val;
    while (cur.next != null) {
        if (cur.next.val < mx) cur.next = cur.next.next;
        else { cur = cur.next; mx = cur.val; }
    }
    return flipList(rev);
}

C++

ListNode* flipList(ListNode* h) {
    ListNode* prev = nullptr;
    while (h) { ListNode* nx = h->next; h->next = prev; prev = h; h = nx; }
    return prev;
}

ListNode* removeNodes(ListNode* head) {
    ListNode *rev = flipList(head), *cur = rev;
    int mx = rev->val;
    while (cur->next) {
        if (cur->next->val < mx) cur->next = cur->next->next;
        else { cur = cur->next; mx = cur->val; }
    }
    return flipList(rev);
}

JavaScript

var flipList = function(h) {
    var prev = null;
    while (h !== null) { var nx = h.next; h.next = prev; prev = h; h = nx; }
    return prev;
};

var removeNodes = function(head) {
    var rev = flipList(head);
    var mx = rev.val, cur = rev;
    while (cur.next !== null) {
        if (cur.next.val < mx) cur.next = cur.next.next;
        else { cur = cur.next; mx = cur.val; }
    }
    return flipList(rev);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 111 stack problems · the whole catalogue

Learn the technique: Stack Data Structure · Monotonic Stack