Linked lists and node identity

A pending-job queue stores linked nodes, and other parts of the app hold references to particular jobs. A customer category is disabled, so all matching jobs must leave the queue. Rebuilding a fresh chain with the same surviving values would leave those references pointing at the old objects.

This is why node identity matters. The task is to reconnect the existing survivors, including when cancelled jobs appear consecutively or at the head.

Removing cancelled jobs without replacing survivors

Filter blocked values while also practicing removal from an actual linked structure. Equal node values do not make their node objects interchangeable: surviving identity is part of the contract.

Building a fresh list of values is a good prototype but cannot satisfy pointer identity. Removing only one matching node fails on adjacent removals; changing a local head variable without returning it loses head updates.

Reconnecting through the predecessor

In 2 → 5 → 5 → 7, removing category 5 means keeping the predecessor at 2 while bypassing both matching nodes. Advancing after the first removal would skip the second. A temporary sentinel before the head gives a head removal the same predecessor-based operation as every other removal. Return its next link, not the sentinel itself.

Value filtering and pointer surgery have different ownership contracts. A value result may allocate new values; detach must retain every surviving Node object. A sentinel removes the head special case, while a previous-survivor pointer ensures adjacent blocked nodes are all skipped. Final filtering and detachment target expected O(n+b) time.

Two objects can have equal payloads and different identities. Java reference comparison is the relevant operation for the pointer tests:

import java.util.*;

class Example {
    public static void main(String[] args) {
        final class Node {
            final long value;
            Node(long value) { this.value = value; }
        }
        Node first = new Node(7);
        Node second = new Node(7);
        assert first.value == second.value;
        assert first != second;
    }
}

The final implementation must return those same surviving references in order, rather than replacements holding equal numbers. A sentinel may simplify link ownership at the head, but its own reference must not appear as a surviving node.

What the links do not make cheap

Identity-preserving removal matters when other indexes, iterators, or owners retain references to nodes. A value-only output hides aliasing errors that an object-oriented interface must make explicit.

prototype and solve return surviving values in order, omitting all blocked values without changing either array. Also implement detach(Node head, Set<Long> blocked) in both stages: relink existing nodes, preserve survivor identity/order, do not mutate blocked, and terminate without a cycle. Null or complete removal returns null. Temporary sentinels are allowed.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

Other components can keep their references to surviving jobs because those nodes were never replaced.