In a single pass over a singly linked list, how do you advance prev and curr while deleting nodes?

### The task A scheduler's run list accumulates expired jobs, and a sweep must purge all of them in one walk. This is where a candidate's grip on pointer discipline shows, because the loop has two jobs at once: it advances through the list, and it mutates the very links it is advancing along. ### The invariant that makes it easy State one sentence before writing anything: **`prev` always references the most recent node that is still in the list.** Everything else follows mechanically. If the current node survives, it becomes the most recent survivor, so `prev` moves onto it. If the current node is removed, the most recent survivor did not change, so `prev` stays exactly where it is. `curr` advances in both cases, because every node is inspected once. ``` prev = nil curr = head while curr != nil: if expired(curr): if prev == nil: head = curr.next else: prev.next = curr.next curr = curr.next // prev deliberately stays else: prev = curr curr = curr.next ``` ### The bug this prevents The tempting compression is to pull the shared advance out of the branch: ``` if expired(curr): prev.next = curr.next prev = curr // wrong: prev may now be a removed node curr = curr.next ``` Trace it on a chain `A -> B -> C -> D` where `B` and `C` are both expired. With `prev = A`, `curr = B`: `B` is expired, so `A.next = C`. Then `prev = B` — but `B` has just left the list. Now `curr = C`, also expired, so the code writes `prev.next = C.next`, that is `B.next = D`. `B` is an orphan; nobody reads it. The live chain still says `A.next = C`, so `C` survives the purge. One expired node slipped through, silently, with no crash and no exception. The defining property of this bug is that it needs **two adjacent removals** to appear. A test that expires one node, or expires alternating nodes, passes. That is the testing lesson worth stating in the interview: the boundary cases for a purge loop are consecutive removals, removals at the front, removals at the end, all nodes removed, and no nodes removed. Only the first of those catches this defect. ### Removals at the front When the first node is expired there is no predecessor to rewrite, so the head reference itself is reassigned. If the next node is also expired, that happens again on the following iteration — hence the guard is `if prev == nil`, evaluated each time, not a one-off pre-loop step. A run of expired nodes at the front is a second boundary case that single-removal tests miss. ### Cost One pass, each node visited exactly once, two references carried: **O(n) time, O(1) extra space**, independent of how many nodes are purged. The alternative that beginners write — repeatedly calling a remove-by-value routine, each of which rescans from the head — is O(n) per removal and O(n*m) for m removals, degrading to O(n^2) when most of the list is expired. Naming that difference is usually the point of the question: the single-pass form is not a micro-optimisation, it is an asymptotic one. ### The same trap in a doubly linked list With back-links there is no `prev` bookkeeping — each node hands you both neighbours — but a related trap replaces it. The removal writes into both neighbours, and if the implementation also clears the removed node's own links (a common hygiene step, and a mandatory one where the node's storage is released immediately), then reading `curr.next` *after* the removal reads a cleared or freed field and the traversal loses the rest of the list. The fix is to capture the successor into a local before mutating: read forward first, mutate second. Both the singly and doubly forms are instances of the same discipline — **decide where you are going before you rearrange where you are.** ### What the interviewer is watching for Not the code. They are watching whether you state the invariant, whether you volunteer the adjacent-removal case unprompted, whether you notice the front-of-list branch has to be inside the loop, and whether you cost the one-pass form against the repeated-search form. A candidate who traces `A -> B -> C -> D` out loud with two adjacent expiries has answered the question completely.