DSA sheet · Linked List · Stack / hash map pattern

Remove Nodes From Linked List

This is the second problem in the linked list + stack pattern, and the teacher solves it four ways, each one fixing a weakness of the one before: (A) copy values into an array and check every pair, (B) the same check done directly on the nodes, (C) a monotonic stack, the "next greater element" trick, which brings the time down to O(n), and (D) reverse + running maximum, which is O(n) time with no extra space. It's a great problem for seeing why a stack turns O(n²) into O(n), and how reversing a list lets you "walk backwards".

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked list basics you need here (node, walking, deleting, dummy node, stack, reversal)
• Part A · Brute force 1: values in an array, check every pair (O(n²))
• Part B · Brute force 2: same check on the nodes, delete with prev (O(n²))
• Part C · Better: monotonic stack (O(n) time, O(n) space)
• Part D · Optimal: reverse + max so far (O(n) time, O(1) space)
• Part E · Revision page

Part 0 · Before starting

What is a linked list node?

A linked list is a chain of nodes. Each node has a value (val) and a link to the next node (next). The first node is the head. The last node's next is None.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

head
 ↓
[5] → [2] → [13] → [3] → [8] → None

Walking, and why there's no index

We walk with a pointer: curr = head, then curr = curr.next until curr is None. There is no list[3]. Reaching position i means walking i steps (O(n)). And we can only walk forward: a node knows its next, not its previous one. Keep that in mind, because this problem is about what lies to the right of each node.

Deleting a node needs the node before it

To remove node X, the node before X must skip over it: prev.next = X.next. Nothing points to X any more, so it's gone from the list. That's why deleting usually needs a prev pointer.

before:  [prev] → [X] → [Y]
after:   [prev] ─────→ [Y]         prev.next = X.next

Save next before changing a pointer

next is the only road to the rest of the list. If you overwrite a.next and haven't kept the old value somewhere, everything after it is lost. Reversal (Part D) is the main place this matters: we save nxt = curr.next before turning the arrow around.

The dummy node

If the head itself must be deleted, there's no node before it, so prev.next = … can't work. Instead of a special case ("move head forward"), we put a fake node in front: dummy = ListNode(0, head). Now every real node has a node before it. The dummy never moves, and at the end the real head is dummy.next, even if the old head was deleted.

[0] → [5] → [2] → [13] → [3] → [8] → None
 ↑
dummy = prev   (start)

A stack

A stack is a pile: you add on top (push) and remove from the top (pop). Last in, first out. In Python a plain list works: st.append(x) pushes, st.pop() pops, st[-1] peeks at the top.

Reversing a list (prev / curr / nxt)

Part D needs the standard reversal from earlier in the sheet. Walk once, and turn each arrow to point backwards. Save nxt first, otherwise the rest of the list is lost.

def reverse(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next      # 1. save the road ahead
        curr.next = prev     # 2. turn the arrow back
        prev = curr          # 3. step prev forward
        curr = nxt           # 4. step curr forward
    return prev              # the old last node is the new head

Part A · Brute force 1: copy values, check every pair

LeetCode 2487 · Remove Nodes From Linked List

1The question in simple words

You get the head of a linked list. Remove every node that has a strictly greater value somewhere to its right. Return the head of what's left.

input:   [5] → [2] → [13] → [3] → [8] → None

5  → there is a bigger value to its right (13)   → remove
2  → 13 is to its right                         → remove
13 → nothing bigger after it (3, 8)              → keep
3  → 8 is to its right                          → remove
8  → it's the last node, nothing after it       → keep

output:  [13] → [8] → None

The teacher points out that for 5 we don't care which bigger value we find (13 or 8). One is enough to delete it. Also, the last node is always kept, because nothing is to its right. And what's left is always non-increasing (13 ≥ 8): if a kept node had a bigger kept node after it, it should have been removed.

2What the constraints tell us

• Nodes: 1 to 10⁵. At least 1 node, so no "head is None" base case is needed.
• n up to 10⁵ means O(n²) = 10¹⁰ operations. The teacher's rule: past about 10⁸ is risky, and 10⁹ or 10¹⁰ will certainly give TLE. So any O(n²) idea will fail. We need a linear solution. (She still shows the O(n²) ones, because that's how we get to the fast one.)
• Values: 1 to 10⁵. A single value fits in an int easily. If we had to add many values, the sum could pass 10⁹ and need a long, but here we only compare values, so no worry.

3Intuition

Pretend it's an array: [5, 2, 13, 3, 8]. For each position i, look at everything to its right (j = i+1 … end). If any value is bigger, i is thrown out. If none is, i survives.

4Building the logic

• Copy the list's values into arr.
• For each i, use a flag (a True/False marker) found = False. Run j from i+1 to the end. As soon as arr[j] > arr[i], set found = True and break. There's no need to look further, since one bigger value is enough.
• After the inner loop: if found is still False, nothing bigger exists to the right, so add arr[i] to the answer.
• Finally build a new linked list from the answer with a dummy node, and return dummy.next.

5Approach steps

1. Copy all values into arr.
2. For each i: scan j = i+1 … n−1. If arr[j] > arr[i], mark found and stop.
3. If not found, append arr[i] to ans.
4. Build a list from ans and return it.

6Code (Python)

class Solution:
    def removeNodes(self, head):
        arr = []
        curr = head
        while curr:                       # copy the values
            arr.append(curr.val)
            curr = curr.next

        ans = []
        n = len(arr)
        for i in range(n):
            found = False                 # is there a bigger value to the right?
            for j in range(i + 1, n):
                if arr[j] > arr[i]:
                    found = True
                    break
            if not found:
                ans.append(arr[i])        # nobody bigger: keep it

        dummy = ListNode(0)
        tail = dummy
        for v in ans:                     # build the answer list
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

7Code line by line

8Dry run

Build → 13 → 8 → None ✓

9Complexity & remember

• Time O(n²): for each i, j can run all the way to the end. The break helps sometimes, but take 5 → 2 → 1 → 1 → …: nothing bigger ever appears, so j scans to the end every time. With n = 10⁵ that's about 10¹⁰ → TLE.
• Space O(n): the value array and the answer.

Part B · Brute force 2: work on the nodes, delete with prev

1The question

Same question. New rule: don't store the values anywhere, play with the nodes directly.

2What the constraints tell us

Same as Part A. This version is still O(n²), so it will also TLE. The goal here is to practise deleting nodes in place.

3Intuition

The same "i and j" idea, but with pointers: curr plays the role of i, and a second pointer temp runs from curr.next to the end looking for something bigger. If it finds one, curr must be removed from the list.

4Building the logic

Deleting needs the previous node → dummy + prev

To delete curr we need prev.next = curr.next. But the head (5) has no previous node. The teacher says we could special-case it by moving the head forward, but why make it complicated? Put a dummy before the head and start prev at the dummy. The dummy never moves, so dummy.next is always the current head.

The scan

For each curr: temp = curr.next, delete = False. While temp exists: if temp.val > curr.val, set the flag and break. Otherwise move temp forward (not curr! we're still looking for something bigger than curr).

After the scan: two cases

• delete is True → prev.next = curr.next. curr is cut out. prev does not move, because the node before the next candidate is still prev.
• delete is False → curr survives, and it will never be deleted. So the safe node before the next candidate is now curr: prev = curr.

Either way, curr = curr.next afterwards.

5Approach steps

1. dummy = ListNode(0, head), prev = dummy, curr = head.
2. For each curr: scan temp from curr.next. Flag if any temp.val > curr.val.
3. Flag → prev.next = curr.next. No flag → prev = curr.
4. curr = curr.next. At the end return dummy.next.

6Code (Python)

class Solution:
    def removeNodes(self, head):
        dummy = ListNode(0, head)        # node before the head
        prev = dummy
        curr = head
        while curr:
            temp = curr.next
            delete = False
            while temp:
                if temp.val > curr.val:  # something bigger to the right
                    delete = True
                    break
                temp = temp.next
            if delete:
                prev.next = curr.next    # cut curr out
            else:
                prev = curr              # curr stays, it is the new safe prev
            curr = curr.next
        return dummy.next

7Code line by line

8Dry run

Snapshot during step 1, when temp finds 13:

[0] → [5] → [2] → [13] → [3] → [8] → None
 ↑     ↑            ↑
prev  curr         temp      → prev.next = curr.next

Return dummy.next → 13 → 8.

9Complexity & remember

• Time O(n²): for every curr, temp may run to the end → 10¹⁰ for n = 10⁵ → TLE. It runs fine on small tests but fails on submit.
• Space O(1): just pointers. We fixed the space problem, but not the time problem.

Part C · Better: monotonic stack

1The question

Same question. Goal: get rid of the inner scan, so the time becomes O(n).

2What the constraints tell us

n = 10⁵ needs O(n) or O(n log n). Extra O(n) memory for 10⁵ nodes is fine.

3Intuition: this is "next greater element"

The teacher's observation: "is there a bigger value to my right?" is the next greater element question from the stack playlist. There, a stack turned O(n²) into O(n). So we use the same tool here.

One twist. In next-greater problems we usually walk from the right, because we need to print the next greater value of each element. Here we don't need that value. We only need to throw away the losers. So the teacher walks from the left: keep a stack of the nodes that survive so far. When a new node arrives, every node on top of the stack that is smaller than it has just found a bigger value to its right, so pop it (delete it).

Picture people standing in a row looking right, where a taller person who arrives later blocks everyone shorter before them. The stack holds the people still "visible". Each newcomer knocks off the shorter people at the top.

4Building the logic

• Walk curr from the head.
• While the stack is not empty and the top node's value is less than curr.val: pop it. It has a bigger value to its right (curr), so it's deleted.
• Push curr, since nobody to its right has been seen yet, and move on.
• At the end, the stack holds exactly the survivors, in original order from bottom to top.

Rebuilding the list from the stack

We don't pop to rebuild (popping would give the nodes in reverse). We just loop over the stack from bottom to top, attaching each node to a tail that starts at a dummy: tail.next = node; tail = node. Return dummy.next.

5Approach steps

1. st = [], curr = head.
2. While curr: pop while st[-1].val < curr.val; push curr; curr = curr.next.
3. Link the stack bottom → top with a dummy and tail. Return dummy.next.

6Code (Python)

class Solution:
    def removeNodes(self, head):
        st = []
        curr = head
        while curr:
            while st and st[-1].val < curr.val:   # smaller ones lose
                st.pop()
            st.append(curr)
            curr = curr.next

        dummy = ListNode(0)
        tail = dummy
        for node in st:                  # bottom to top = original order
            tail.next = node
            tail = node
        return dummy.next                # the last node's next is already None

7Code line by line

8Dry run: watch the stack

The bottom is listed first and the top is in red. Rebuild bottom → top: dummy → 13 → 8 → None ✓

9Complexity & remember

• Time O(n). It looks like a loop inside a loop, but the teacher explains why it isn't n²: each node is pushed once and popped at most once. Worst case 5 → 4 → 3 → 2 → 6: four pushes with no pops, then 6 pops all four at once. Total about 2n operations, so O(2n) = O(n).
• Space O(n): in the worst case (a non-increasing list like 5 → 4 → 3 → 2) every node stays in the stack.

Part D · Optimal: reverse + "max so far"

1The question

Same question. Goal: O(n) time and no extra space (no stack).

2What the constraints tell us

O(n) passes for 10⁵. We are allowed to change the input list (we already did in Part B).

3Intuition: look from the right

The question is about what's on the right. If we stand at the right end and walk left, we can carry one number: the biggest value seen so far. Any node smaller than that max has a bigger value to its right, so delete it. Any node ≥ max stays, and becomes the new max.

But a singly linked list can't walk left. The teacher's fix: reverse the list first. Now "walking forward" in the reversed list means walking right-to-left in the original. When we're done deleting, reverse it back.

original:  [5] → [2] → [13] → [3] → [8] → None
reversed:  [8] → [3] → [13] → [2] → [5] → None
           max starts at 8 (the original last node always stays)

4Building the logic

Look at curr.next, not curr → no prev needed

Deleting normally needs a prev. The teacher avoids that: stand on curr and judge the node after it. If curr.next.val < mx, delete it with curr.next = curr.next.next. curr itself is the "previous" node.

Don't move curr after a deletion

After skipping one node, the new curr.next might also be small (in the reversed list 13 → 2 → 5, both 2 and 5 are smaller than 13). So after a delete, we stay on curr and check again. Only when curr.next survives do we move: curr = curr.next, and update mx = curr.val.

The loop condition: curr and curr.next

We read curr.next.val, so curr.next must exist. The loop runs while both exist.

The first node of the reversed list always survives

It's the original last node, which nothing can beat. So we start curr and mx there, and the reversed head never changes. We save it as head before the loop, then reverse back at the end and return the new head.

5Approach steps

1. head = reverse(head).
2. curr = head, mx = head.val.
3. While curr and curr.next: if curr.next.val < mx → curr.next = curr.next.next; else → curr = curr.next, mx = curr.val.
4. Return reverse(head).

6Code (Python)

class Solution:
    def reverse(self, head):
        prev, curr = None, head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

    def removeNodes(self, head):
        head = self.reverse(head)        # now we can walk right-to-left
        curr = head
        mx = head.val                    # the original last node: always kept
        while curr and curr.next:
            if curr.next.val < mx:       # a bigger value exists to its right
                curr.next = curr.next.next   # delete it, stay on curr
            else:
                curr = curr.next         # it survives
                mx = curr.val            # and it is the new biggest
        return self.reverse(head)        # back to the original direction

7Code line by line

8Dry run (reversed list 8 → 3 → 13 → 2 → 5)

Snapshot at step 3:

[8] → [13] → [2] → [5] → None       mx = 13
        ↑      ✗
       curr   curr.next (2 < 13 → skip it)

9Complexity & remember

• Time O(3n) = O(n): reverse (n) + one pass deleting (n) + reverse back (at most n).
• Space O(1): just a few pointers, no stack, no array.

Stack or reverse, which one? The teacher's rule of thumb:

• If changing the list is allowed and memory is tight → reverse + max (Part D).
• If memory is fine but you shouldn't disturb the list → stack (Part C).

Part E · Revision page

def build(vals):
    dummy = ListNode(0)
    t = dummy
    for v in vals:
        t.next = ListNode(v)
        t = t.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.removeNodes(build([5, 2, 13, 3, 8]))))   # [13, 8]
print(to_list(s.removeNodes(build([1, 1, 1, 1]))))       # [1, 1, 1, 1]
print(to_list(s.removeNodes(build([5, 4, 3, 2, 6]))))    # [6]

Based on this video: Remove Nodes From Linked List