After the split-and-reverse symmetry check answers, what state is the caller's linked chain in?
answer
- a question should not change the world
- who else holds this chain
- reversing twice is an identity
- the early exit skips the cleanup
- restore on every path out
basics
~20 sUnless the back half is reversed a second time before returning, the caller is handed a mangled chain whose second half still runs backward. Restore it on every exit path, including the early return on the first mismatch.
solid answer
~40 sThe check reads like a query but is a command: reversing the back half in place rewires the caller's own links, so a routine that returns the verdict and stops leaves the second half running the wrong way and the front half's tail pointing at the old last node. A production version reverses the back half again and reattaches it before returning — cost is one more linear pass, so it stays O(n) time and O(1) extra space. The bug interviewers actually look for is the `return false` inside the comparison loop, which jumps out before the cleanup; the fix is to record the verdict, break, restore unconditionally, then return. Even with a perfect restore there is a window in which the structure is invalid, which is the real price of the constant-space version.
code
pseudocode · 11 lines// is_symmetric(head): chain of probe base records
mid = find_middle(head) // last node of the front half
back = reverse(mid.next) // back half, now walkable inward
front = head
p = back
while p != null:
if p.base != front.base:
return false
p = p.next
front = front.next
return truego deeper
Know that reversing half a chain in place really does change the caller's structure, and that reversing it a second time puts it back. Say so before the interviewer has to ask.
Walk both exit paths — first mismatch and full match — and show the restore running on each. Explain why the extra pass leaves the time and space bounds unchanged.
Treat it as an API contract: a query that mutates its input is a defect. Name the window in which any other holder of the chain observes a half-reversed structure.
Decide when a routine may mutate shared structure at all and make that rule explicit for the team: constant space in a hot private path, a non-mutating copy anywhere the chain is shared.
## A query that is secretly a command The constant-space symmetry check on a singly linked chain gets its constant space by rewiring links that belong to the caller. There is no copy, no scratch buffer — the O(1) is bought by editing the input. That makes the routine a *command* wearing the clothes of a *query*, and the difference shows up the moment the caller tries to use its chain again. Walk the fragment above with a caller's eyes. Suppose the chain holds five base records `A T G T A`. After the split, the front half ends at `G`. After `reverse(mid.next)`, the segment `T A` has become `A T`, and the structure now reads `A T G` with `G`'s successor being `T` (the old last node), which terminates. The comparison walks `A T` against `A T` from the head and returns true. And then the routine returns — leaving the caller holding `A T G T A` in name only. Its actual link order is now `A T G T` with the tail lost from the front-to-back walk, because the node that used to be last now points at nothing. The caller did not ask for that. They asked a yes/no question. ## The restore The fix is mechanical: reverse the back half a second time and reattach it where it was. Reversing a segment twice is an identity, so the chain comes back exactly as it was handed over. What it costs: one more pass over at most half the nodes. The routine was already O(n) time and it stays O(n); it was already O(1) extra space and it stays O(1), because the restore allocates nothing. The constant factor rises by roughly half a pass. Anyone who claims the restore "makes it O(n log n)" or "needs a copy" has confused an extra linear pass with an extra factor. ## Where the restore gets skipped Not on the success path — people remember the cleanup they wrote at the bottom. It gets skipped on the **early exit**: a `return false` fired the instant two values differ. That path is the common one on real inputs (most chains are not symmetric), so the bug ships and then fires on almost every call. Two disciplines fix it: - **Single exit.** Record the verdict in a local, `break` out of the comparison, run the restore unconditionally, then return the local. The comparison loop no longer contains a `return`. - **Guaranteed cleanup.** Wrap the mutating region in whatever construct the setting provides for running cleanup on every way out, including an error propagating up from a comparator. If the values being compared can throw, an ordinary restore-at-the-bottom is not enough. ## The window nobody can restore away Even a flawless restore leaves a period — between the reversal and its undo — during which the chain is not a valid representation of the caller's data. Whether that matters depends on who can look: - An iterator created before the call and advanced after it walks into a segment that has been rewired underneath it. - A comparator that calls back into user code can observe the chain mid-check. - Any other holder of a reference into the back half sees links pointing the wrong way. - A concurrent reader sees garbage, and no restore-later helps at all. This is the honest boundary of the constant-space trick: it is safe when the routine owns the chain for the duration and nothing else can look in. When that is not guaranteed, the professionally correct answer is to copy the values out and never touch the structure — trading O(n) space for the removal of an entire class of bugs. ## The interview register Saying "and then I reverse the second half back before returning, including on the mismatch path" is a small sentence that separates candidates sharply. It shows you thought about the caller, not just the algorithm; it shows you know which exit path is the buggy one; and it sets up the follow-up about whether in-place mutation of shared structure is acceptable at all. Volunteer it rather than waiting to be asked — being asked means the interviewer already noticed you missed it.
- Does restoring the reversed half change the routine's complexity?No. The restore is one more reversal of at most half the nodes, so the routine stays O(n) time and O(1) extra space; only the constant factor moves, by roughly half a pass. Anyone who says the restore introduces a logarithmic factor or requires a copy has confused an additional linear pass with an additional factor. If a reviewer objects, the objection is about readability, not about the bound.
- What can go wrong if something else reads the chain while the check is running?It observes a structure that is temporarily not the caller's data: the back half runs the opposite way, and the front half's tail points at the old last node. Even single-threaded, an iterator created earlier or a callback fired from the value comparison sees the corruption. A concurrent reader sees it too, and no later restore helps. That window is the true cost of the in-place approach, restore or not.
- How would you make the restore survive an early exit or a throwing comparison?Take the `return` out of the comparison loop: record the verdict in a local, break, restore unconditionally, then return the local. If comparing two values can raise an error, put the mutating region inside whatever guaranteed-cleanup construct the setting offers, so the chain is repaired on the error path too. The classic shipped bug is the mismatch exit that jumps straight out past the cleanup.
saying these in an interview costs you the question
- Returns the verdict and leaves the chain reversed
- Restores only on the match path, not on mismatch
- Claims the restore worsens the time complexity
- Says in-place is always safe because it restores
- Assumes the caller no longer needs the chain