When is copying a linked chain into an array the better symmetry check than the O(1)-space one?

## The two candidates, stated fairly **Copy out.** Walk the chain once, collecting values into a growable array. Compare with converging indices. O(n) time, O(n) extra space. The chain is never touched. **In place.** Split at the middle, reverse the back half, compare in lockstep, reverse the back half again to restore. O(n) time, O(1) extra space. The chain is edited and then repaired. Note what is *not* on the table: a time difference. Both are linear, both make a small constant number of passes. Anyone arguing this trade on speed has misread it. ## What the constant space actually costs 1. **A cleanup obligation on every exit path.** The mismatch return, the loop's normal end, and any error raised while comparing two values all have to leave the chain repaired. The version people write first repairs it on exactly one of those paths. 2. **A window of invalidity.** Between the reversal and its undo, the structure is not what its owner believes it is. If any other party can look during that window — an iterator held elsewhere, a comparator that calls back into user code, another thread — it observes corruption, and no amount of restoring afterwards helps. 3. **Review cost.** The in-place version is three subroutines' worth of pointer surgery whose correctness rests on invariants that do not appear in the code. The copy version is a loop and a comparison. On a team where the second-least-experienced person will one day change this function under time pressure, that difference is a real, ongoing expense. ## What the linear space actually costs Be equally honest in the other direction. "O(n) space" sounds severe and often is not: the array holds one value or one reference per node, on a structure that already pays a link per node. The overhead can be a fraction of the structure being examined. It becomes serious when - the chain length is unbounded and driven by external input, - many such checks run at once, so the peak is a multiple of one array, - the environment has a hard per-process or per-device memory ceiling, or - allocation itself is the expensive thing in that path — an allocation on a hot path can cost more than the pointer surgery it replaces. That last one is why "constant space" sometimes wins on *latency* rather than on memory. ## The decision, as a rule you can hand to a team Use the non-mutating copy by default. Reach for the in-place version only when all of the following hold, and write down that they hold: - The routine owns the chain for the duration; nothing else can observe it. - The path is hot enough or the memory ceiling tight enough that O(n) auxiliary space is genuinely a problem, measured rather than assumed. - The restore is unconditional — no `return` inside the mutating region, and errors are covered. Writing the rule down is the principal-level move. Left to individual judgment, every author re-derives the trade from scratch, and half of them re-derive it as "constant space is better, obviously", which is how a query that silently mutates its input reaches production. ## The interview version of the same question The loop is testing whether you know the in-place trick, so produce it. But produce it with the trade attached: one sentence for the array baseline to establish you have a correct, simple answer; the in-place construction as the main answer; then the caveat about the mutation window and the restore. Candidates who only know the trick sound identical to candidates who understand it right up to the moment the interviewer asks "any downside?" — and that question is the entire point of asking. A fourth position is worth having ready: for a structure that is examined this way often, the right move may be neither, but a change of representation — keep the sequence in a form with random access, or maintain the symmetry answer incrementally as elements are appended. Redesigning the input away from a singly linked chain is frequently the cheapest fix available, and noticing that is a different skill from executing either algorithm.