Reversing a whole list changes its head. Reversing only a middle segment has two additional obligations: reconnect its predecessor to the new segment head, and reconnect its old head to the unchanged suffix. A pointer diagram makes these obligations visible before any code is written.
This chapter extends the course material on pointers, memory and structs and lists as recursive ADTs. The in-place pointer algorithm is a derived application; it is not a claim that the functional ADT uses mutation.
Contract and algorithm
Definition 2.3.1
(Segment reversal contract)
The input is a finite, acyclic singly linked list of distinct nodes. Each node has a next reference and a value. Positions are one-based and satisfy . Reverse the order of nodes in positions through ; retain the nodes, values, and order outside the segment. Return the possibly changed head. No node is allocated or freed during the operation, aside from a temporary dummy record that is not a list node in the returned result. Assume exclusive permission to mutate the segment nodes' next fields and, when , the predecessor's next field; external aliases to nodes remain aliases but may observe these changed fields.
reverseSegment(head, l, r): # precondition: 1 <= l <= r <= n
dummy.next = head
before = reference to dummy
repeat l-1 times:
before = before.next
first = before.next
after = first
repeat r-l+1 times:
after = after.next
prev = after
curr = first
while curr != after:
next = curr.next
curr.next = prev
prev = curr
curr = next
before.next = prev
return dummy.next
The dummy is a temporary record with a next field. When , before is the dummy, so the same final assignment updates the returned head. When , after is null; setting prev = after makes the original segment head end at null after reversal. The pointer after is found before links are changed. The variable next is saved before rewriting curr.next, so the unprocessed part remains accessible.
Why this reverses exactly the intended nodes
Theorem 2.3.2
(Correctness of segment reversal)
Let the list consist of distinct nodes and let . Then reverseSegment(head, l, r) returns the head of the list , allocating and freeing no list node. It makes pointer steps and uses auxiliary references.
Proof
(An invariant for the reversed prefix of the segment)
Write the original segment as , where and , followed by the unchanged suffix beginning at after. After iterations, , prev heads the chain when , and equals after when . If , curr points to , and the unprocessed links still lead through to after; if , curr == after.
Initially , so the invariant holds. One iteration saves the next unprocessed node, makes point to the reversed prefix, then advances both references. This grows the reversed prefix by exactly one node while preserving the remaining chain. At the loop stops, and prev points to . Assigning before.next = prev joins the unchanged prefix to that chain. Thus every original node remains exactly once in the returned list and the suffix is preserved. The nodes are never written to, apart from the single assignment to before.next, and the suffix from after onward is only read, so the returned list is exactly the one in the statement.
During the loop, the list reachable from the old head need not yet be the final list; curr and prev are necessary working references. Concurrent readers observing intermediate links are outside this sequential contract.
Proof X-ray
What keeps the unprocessed nodes reachable?
After the first rewrite, following the old segment head leads to the saved suffix, not to the remaining segment. The local reference curr preserves the next unprocessed node. Meanwhile prev ends at after, so when the loop finishes the old segment head already reconnects to the unchanged suffix; the final assignment only reconnects the predecessor.
Worked examples
Worked example 2.3.3
(Reversing the middle of five nodes)
For distinct nodes , let . The predecessor is , first is , and after is . Initially prev=E, curr=B. The three iterations build B -> E, then C -> B -> E, then D -> C -> B -> E; curr has reached . Finally set A.next=D. The returned chain is . The suffix starts at the same node , not a copy of its value.
Worked example 2.3.4
(A segment that starts at the head)
For distinct nodes , let and . Then before is the dummy, first is and after is . Initially prev=C and curr=A. Iteration 1: next=B, A.next=C, prev=A, curr=B. Iteration 2: next=C, B.next=A, prev=B, curr=C, which equals after, so the loop stops. Setting dummy.next=B and returning it gives . The caller's old head, which is , is now the second node, so the caller must use the returned head.
Worked example 2.3.5
(Edge cases: a segment that ends at the tail, and a one-node segment)
Take with and . Here before is and first is . Finding after takes three steps from : , then , then null. So prev starts as null. The loop sets , then , then , ending with curr null, equal to after. Then A.next=D gives : the segment's old head now ends the list.
Now take with . Then first=B, after=C and prev=C. The single iteration sets B.next=C, prev=B, curr=C. The assignment A.next=B changes nothing: a one-node segment reversed is itself.
Errors to avoid
Common mistake
(Starting prev at null as in whole-list reversal)
Using prev = null, as in whole-list reversal, cuts off the suffix. For with and , the first iteration sets B.next=null, and the final list is . Node is lost. Starting prev at after is what reconnects the segment's old head to the suffix.
Common mistake
(Forgetting the final reconnection)
Without before.next = prev, the predecessor still points to the old segment head. For with and , the reversed chain exists, but A.next is still , and is now . The result is ; nodes and are unreachable from the head.
Counterexample mode
Positions beyond the end are not harmless
A plausible claim is that, since the search for after simply stops at null, a position merely reverses up to the end. Take with and . Then first is and the search for after must take steps: the first reaches , the second reaches null, and the third tries to read null.next. The walk fails before any link is changed.
The precondition is part of the contract. Checking it would require counting the nodes first, which is extra work and a separate contract.
Cost and limits
Locating before and after takes pointer steps; reversing takes iterations, so total time is and is in the worst case. The algorithm uses auxiliary references, excluding the existing list. These bounds assume constant-time pointer operations and valid positions; checking arbitrary invalid positions or detecting input cycles requires a separate contract and possibly extra work. Values need not be distinct because positions and node identity, not value equality, determine the segment.
Exercises with solutions
Quick check
(For and , what does the algorithm return?)
Which node is first, and what is after?
Solution · Answer
The list is unchanged, . Here first is and after is . The single iteration sets C.next=D, so prev is , and B.next=C restores the original link. A one-node segment reversed is itself.
Quick check
(For , and , how many pointer steps locate before and after, and how many iterations does the loop make?)
Count the steps of each search separately.
Solution · Answer
Locating before takes step, from the dummy to . Locating after takes steps, from to . Together this is steps. The loop runs times.
Quick check
(Why does the function return dummy.next rather than head?)
What happens to the old head when ?
Solution · Answer
When , the old head is the first node of the reversed segment, so after the reversal it is no longer first. The new first node is stored in dummy.next by the final assignment. In the example with , , head is but the correct result is .