NeetCode #318LC-2487MediumLinked List
← Back to All Problems#318 · #2487 · Remove Nodes From Linked List(从链表中移除节点)
📌 Problem Statement & Constraints
You are given the head of a linked list. Remove every node that has a node with a greater value somewhere to its right. Return the head of the modified list. Constraints: the number of nodes is in
[1, 10^5], 1 <= Node.val <= 10^5.💡 Core Algorithmic Approaches
- Reversing the list turns "greater value to the right" into "greater value seen so far", which is a running maximum.
- After reversing, keep a node only when its value is at least the maximum seen so far.
- Reverse the kept list back to restore the original orientation.
- A monotonic stack over the list achieves the same in one pass without reversal, but the reverse-filter-reverse approach is easier to verify.
💻 Benchmark Python3 Implementation
class Solution:
def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(node):
prev = None
while node:
node.next, prev, node = prev, node, node.next
return prev
head = reverse(head)
dummy = tail = ListNode(0)
cur = head
mx = 0
while cur:
if cur.val >= mx: # a new running maximum -> keep
mx = cur.val
tail.next = cur
tail = cur
cur = cur.next
tail.next = None # terminate the kept list
return reverse(dummy.next)
# Monotonic-stack variant: no reversal, one pass
class Solution2:
def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
st = []
cur = head
while cur:
while st and st[-1].val < cur.val:
st.pop() # the popped node has a greater value to its right
st.append(cur)
cur = cur.next
for i in range(len(st) - 1):
st[i].next = st[i + 1]
st[-1].next = None
return st[0]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one or two passes.
💾 Space Complexity
O(1) for the reversal version; O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Using
>instead of>=: equal values are allowed to survive, since only a greater value to the right disqualifies a node. - Forgetting to terminate the kept list:
tail.nextmust be set toNone, otherwise the discarded nodes remain attached. - Comparing against the wrong direction: without the reversal, the running maximum must be computed from the right, which requires extra bookkeeping.
- Mutating values: the nodes are relinked, not rewritten.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.