In the split-reverse-interleave reorder of a linked chain, which half gets the odd extra node?

## The target shape Take a print queue held as a singly linked chain and rearrange it so jobs alternate from the two ends inward: first job, last job, second job, second-to-last job, and so on. The constant-space construction has three moves: 1. **Split** the chain into a front half and a back half. 2. **Reverse** the back half in place, so its last job becomes the head of that segment. 3. **Splice** alternately: one front node, one back node, one front node, one back node, until the back half is used up. All three moves rewire existing links, so the whole reorder is O(n) time and O(1) extra space. ## The invariant the splice depends on Look at one iteration of the splice loop in the fragment: it saves both successors, points the current front node at the current back node, points that back node at the saved front successor, then advances both pointers. Every iteration consumes **exactly one node from each half**, and every back node is placed **after** a front node. That gives the invariant directly: *the front half must never be shorter than the back half*. If the two are equal (even `n`), the loop consumes them together and both pointers land on null at the same moment. If the front half is one longer (odd `n`), the loop stops when the back half runs out, and the surviving front node is the last one placed — the tail of the result — which is exactly where the middle job belongs in the alternating order. So: **ceil(n/2) in front, floor(n/2) behind.** ## Trace it on five jobs Jobs `a b c d e`. Split gives front `a b c`, back `d e`; reversing the back half gives `e d`. - Iteration 1: save `b` and `d`; link `a -> e`, `e -> b`; advance to front `b`, back `d`. - Iteration 2: save `c` and null; link `b -> d`, `d -> c`; advance to front `c`, back null. - Loop ends. `c` is the front half's tail, already terminating. Result: `a e b d c` — first, last, second, second-to-last, middle. Correct. ## Now give the extra node to the back half Same five jobs, front `a b`, back `c d e` reversed to `e d c`. - Iteration 1: link `a -> e`, `e -> b`; front `b`, back `d`. - Iteration 2: `b` is the front tail, so its successor is null; link `b -> d`, `d -> null`; front becomes null, back becomes `c`. - The loop condition still holds — the back half is not exhausted — so iteration 3 reads `front.next` on a null front. Depending on the environment that is a crash, and in a variant of the loop written to guard against it, node `c` is simply dropped from the result. One node of misallocation, two different production failures. That is why the parity convention is not cosmetic. ## The second trap: cutting the front half Splitting is not just "note where the middle is". The front half's last node must be terminated. If it is left pointing at the first node of the back half, then after the splice that stray link points at a node the loop has already placed somewhere earlier in the result. Traversing the finished chain walks forward into a node it has already visited and never terminates — a cycle, produced by an omission that looks like tidiness. The symptom in a real service is a request that hangs rather than one that fails, which is strictly worse to diagnose. ## Which pointer drives the loop Drive the loop from the **back-half pointer**. When it hits null, every back node has been placed and the front half is either exhausted (even `n`) or holding exactly the leftover tail (odd `n`). Driving from the front pointer instead re-introduces the parity as a special case you must code by hand, and that is where the double-placed node and the dropped tail come from. ## The alternative worth naming If O(n) extra space is acceptable, walk the chain once collecting node references into an array, then relink them by taking references alternately from the front and the back of the array. It is much easier to get right, has no parity subtlety at all beyond a single loop bound, and mutates nothing until the final relink. The in-place version earns its keep when the chain can be long and memory is the binding constraint — not because it is more elegant to read, because it is not. ## What to say "Front half takes the extra node, so it is never shorter than the reversed back half; the splice consumes one from each per step; the loop is driven by the back half so odd length needs no special case; and the front half's tail is terminated at the split, or the result closes a cycle."