⚡Flashcard Drill➔
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

  1. Reversing the list turns "greater value to the right" into "greater value seen so far", which is a running maximum.
  2. After reversing, keep a node only when its value is at least the maximum seen so far.
  3. Reverse the kept list back to restore the original orientation.
  4. 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.next must be set to None, 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.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems