Given only a node in a singly linked list and no head, how do you remove it and when does that fail?

### The constraint A cancellation handler in a scheduler is often handed exactly one thing: the run-list node for the job being cancelled. No head reference, no predecessor, no index. The instinct is that this is impossible in a singly linked list — the removal is a write into the predecessor, and the predecessor is unreachable from a forward-only node. That instinct is correct about the *node* and wrong about the *problem*. ### Reframing: remove the position, not the object A list is a sequence of payloads. Nobody outside the implementation can tell which physical node carries which payload — only the order of payloads is observable. So instead of detaching the node you hold, shift its successor's payload backwards into it and detach the successor: ``` node.payload = node.next.payload node.next = node.next.next ``` Two writes, O(1), no predecessor consulted. The chain is one node shorter and the sequence of payloads is exactly the sequence with the target's payload removed. The node object you were handed is still linked in — it now impersonates its former successor — and the object that actually left the list is the successor. ### Where it breaks: the last node If the node you hold is the last one, `node.next` is nil. There is no payload to shift backwards, and detaching the node itself still requires the predecessor you do not have. This is not a coding oversight to patch; it is an information-theoretic limit of the setup. With a forward-only chain and a single node reference, the last position cannot be removed. Interviewers ask the copy trick almost entirely to get to this follow-up, so lead with it rather than waiting to be caught. The usual attempted patch — setting the node's own forward link to nil — does nothing, because the node was already the last one and its predecessor still points at it. Marking the payload as empty is closer but changes the observable sequence's length only if every reader agrees to skip empties, which is exactly the fallback below made explicit. ### The second failure: node identity The trick assumes no one else cares which physical node holds which payload. That assumption fails whenever node identity is externally visible: - Another cursor parked on the successor is now sitting on a node that is no longer in the list, and it will walk off into whatever the orphan still points at. - A registry mapping job identifiers to nodes — the very thing that let the handler hold a node in the first place — now maps the successor's identifier to a node that has left the list, while the successor's payload lives in a different node. - Any code holding the node as a stable handle for the job sees its payload change underneath it. In a scheduler that hands out node references as cancellation handles, this second problem is usually more damaging than the last-node problem, because it corrupts silently rather than failing loudly. Say this out loud; it separates candidates who memorised the trick from candidates who understand what it costs. ### The honest fallback: mark dead and reap When node identity matters, or the last position must be removable, the production answer is to stop removing eagerly. Give each node a dead flag; cancellation writes the flag, which is unconditionally O(1) at any position, including the last, and never touches a link. Traversals skip flagged nodes, and a pass that is already walking the list — the scheduler's own dispatch sweep — unlinks them properly using the predecessor it is carrying anyway. That choice is not free, and the interviewer will push on it: dead nodes occupy memory and are still visited by every traversal until reaped, so the design needs a policy answering *who reaps and how often*. Without one, a cancel-heavy workload grows the list without bound and turns every dispatch sweep into a walk over mostly-dead entries. The compensating benefit is a genuinely constant-time, always-correct cancellation path, which is usually the latency the scheduler actually cares about. ### Summary of the three options | Approach | Cancel cost | Works on last node | Preserves node identity | | --- | --- | --- | --- | | Payload copy + splice successor | O(1) | No | No | | Search for predecessor from head | O(n) | Yes | Yes | | Mark dead, reap in a later pass | O(1) | Yes | Yes | The copy trick is a genuine, correct technique with a sharply defined domain. Knowing its two failure modes — the last position and observable node identity — is what the question is actually testing.