Why can't a singly linked chain be palindrome-checked by converging pointers from both ends?

## The obstacle A symmetry check compares position `i` against position `n-1-i`. On a randomly accessible sequence that is trivial: two indices, one moving up, one moving down, meeting in the middle, O(n) time and O(1) extra space. A singly linked chain gives you neither ingredient. Each node stores a value and exactly one link to its successor. There is no link to a predecessor, and there is no arithmetic that turns "position `n-1-i`" into a node — the only way to reach a position is to walk to it from the head, which makes the naive two-ended version O(n) per comparison and O(n^2) overall. So you have three families of answers, and an interviewer wants you to know all three and to say which one you are choosing. ## 1. Copy the values out (O(n) space) Walk the chain once, appending each value to a growable array (or pushing each onto a stack). Now you have random access, so run the converging-index comparison, or compare the array against the stack popped in reverse. O(n) time, O(n) extra space, and — the property that matters in real code — it does not touch the chain at all. ## 2. Recurse to the tail (O(n) space, hidden) Recurse forward to the end; as each call returns, compare the node it owns against a shared front pointer that you advance one step per return. This genuinely compares back-to-front without any explicit container, and candidates often present it as "constant space". It is not. Recursion depth **is** space: one stack frame per node means O(n) auxiliary space, plus the risk of exhausting the stack on a long chain. The container was not removed, only relocated into the call stack. ## 3. Split, reverse the back half, compare (O(1) space) This is the answer the question is usually testing. 1. **Split.** Find the node where the front half ends, and treat everything after it as the back half. 2. **Reverse the back half in place.** Rewire its links so the old last node becomes the head of that segment. Now the back half is walkable in the direction that a mirror comparison needs, without a single backward pointer having been invented. 3. **Compare.** Run one pointer from the head of the chain and one from the head of the reversed back half, comparing values in lockstep. Time is O(n): a pass to split, a pass to reverse half, a pass to compare half. Extra space is O(1): reversal only rewires existing links, and the routine holds a fixed number of pointers. ## Why the comparison is driven by the back half The two halves are not the same length when `n` is odd. Whichever convention the split uses, one half is one node longer, and that extra node is the middle element — which is its own mirror image and never has to match anything. Driving the loop from the reversed back half (stop when it is exhausted) makes that fall out for free: you compare exactly floor(n/2) pairs and never touch the middle. Driving it from the front pointer instead is the classic off-by-one — you either compare the middle against something it should not be compared against, or walk the front pointer past the split. Even length has no middle node, and the same loop condition still stops after exactly n/2 pairs. One loop, both parities, no special case. ## The price of phase 2 Reversal is destructive. Between the moment you rewire the back half and the moment you rewire it back, the caller's chain is not the chain they handed you: the second half runs the other way, and the front half's tail points at what used to be the last node. If the routine returns without undoing that, the caller receives a mangled structure from what looked like a read-only question. If anything else can observe the chain during the check — an iterator held elsewhere, a callback fired from the comparison — it sees the corruption even if you restore perfectly afterwards. That is the real trade, and it is why option 1 is not a beginner's answer to be embarrassed about: O(n) space buys a check that mutates nothing, has no cleanup path to forget, and can be reviewed at a glance. The constant-space version buys memory at the cost of a window in which a shared structure is briefly invalid. ## What to say out loud "Forward-only links rule out the two-ended trick. With linear extra space I copy the values out and compare converging indices. To get constant space I split at the middle, reverse the back half in place, compare in lockstep driven by the back half so an odd middle is skipped, and then reverse the back half again to hand the caller back what they gave me."