Reversing a linked-list segment between positions m and n: which boundary links must you rewire?

## The shape of the problem A moderation tool has to un-reverse a corrupted stretch of a notification feed: everything outside positions m through n must stay exactly as it is, and the records inside must come back in the opposite order. The interior is the reversal you already know. What makes this a different question is the two seams, and the fact that you must still be holding the right four nodes when the interior loop stops. ## The four references - **before** — the node at position m − 1, the last node that keeps its link direction. After the operation it must point at the segment's new head. - **old m-th** — the segment's first node. After reversal it is the segment's *tail*, and it must point at whatever followed position n. - **old n-th** — the segment's last node. After reversal it is the segment's *head*. - **after n** — the first node outside the segment on the right. It is untouched, but you need its identity to reattach the tail. Only two links are actually written at the seams: `before → old n-th` and `old m-th → after n`. The other two references exist so you can name those two endpoints when the moment comes. ## The dummy node earns its place here When m is 1, there is no node before the segment, and the head of the whole list changes. Without a guard, that becomes a special case with its own branch — and special cases in pointer code are where bugs live. Placing a dummy node in front of the head makes `before` always exist: for m = 1 it is the dummy itself, and the new head is simply read off `dummy.next` at the end. One extra node removes an entire branch, and it is the reason to return `dummy.next` rather than the original head reference, which is stale whenever the segment includes position 1. ## Running the interior loop the right number of times After the walk, set `prev = null` and `curr = before.next`, then run the standard body exactly n − m + 1 times — the number of nodes in the segment, inclusive of both ends. Off-by-one here is the classic failure: n − m steps leaves the last node unreversed and the stitch attaches the wrong node; n − m + 2 steps drags one node in from outside the segment. One detail people miss: on the loop's very first step, the old m-th node's link is set to `prev`, which is null. So from that moment the segment's tail points at nothing, and the right-hand part of the list is held **only** by `curr` as the loop advances. Lose that and the feed ends at position n. ## The stitch, and why its order is not free When the loop stops, `prev` is the old n-th node and `curr` is the node after n. Crucially, `before.next` has not been touched by the loop at all — it still names the old m-th node, which is now the segment's tail. That gives: ``` before.next.next = curr // tail of segment reattaches to the right side before.next = prev // left side attaches to segment's new head ``` Do it in the other order and `before.next` now names the old *n*-th node, so `before.next.next = curr` overwrites a link inside the reversed segment and points the segment's head straight past its own body. The old m-th node still points at null, so the list ends at the wrong place and the remaining records are dropped. The general discipline is the same one that governs whole-list reversal: read every reference you need out of a link *before* you overwrite that link. ## Edge cases worth stating before you write - **m == n** — a one-node segment. The loop runs once, `prev` is that node and `curr` its successor, and the stitch puts everything back exactly as it was. It works without a special case, which is a good sanity check on your loop bounds. - **m == 1** — handled by the dummy, as above; remember to return `dummy.next`. - **n == length** — `curr` ends as null and the segment's tail correctly points at nothing. Again no special case, provided the loop condition counts steps rather than testing for null. - **Invalid input** — m > n, or n past the end. Decide up front whether you validate or assume; saying "I'd assume 1 ≤ m ≤ n ≤ length and validate at the boundary" is a complete answer. ## Cost The walk to position m is O(m) and the reversal is O(n − m + 1), so the total is O(n) in the worst case — the whole list, when the segment sits at the end. A common wrong answer is O(k) for a segment of length k: the segment work is O(k), but you cannot reach position m without walking there, because a singly linked list offers no random access. Auxiliary space is O(1): a fixed handful of references plus the dummy node, none of which grows with the list. Everything is done in one pass over the prefix and one pass over the segment, so no second traversal is needed.