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.
- Difficulty: Medium
- Topics: Stack, Monotonic Stack, Recursion
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
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.
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?
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
- Reverse the list. Its first node (the original last) always survives; set
mxto its value. - Walk the reversed list: if the next node's value is below
mx, unlink it; otherwise move onto it and setmxto its value. - 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