Lists are finite, acyclic and singly linked; positions are one-based and valid. Use the algorithm and dummy-node convention in the teaching chapter.
Roadmap. Identify before, first and after before rewriting links. Trace the saved next reference and reversed prefix. Reconnect the predecessor only after the loop.
Checklist. Save curr.next before changing it. Initialize prev to after. If , return the dummy's updated next; if , after is null. Original nodes and suffix must survive.
1. Trace a middle segment
Exercise
(For , reverse positions 3 through 5. Give before, after, and the values of prev and curr after each loop iteration; write the returned chain.)
Core
Hint(1)
Locate
beforeandafterfirst, and startprevatafter.
Solution(3)
- 1
Locate the boundary nodes
before=Bandafter=F. Initiallyprev=Fandcurr=C. - 2
Run the three iterations
Key step
After the first iteration
prev=C,curr=D, with . After the secondprev=D,curr=E, with . After the thirdprev=E,curr=F, with .Because: Each iteration saves
curr.nextbefore rewriting it. - 3
Reconnect the predecessor
Since
curr == after, stop and set . The returned chain is .
2. A changed head
Exercise
(A list contains distinct nodes with values . Reverse positions 1 through 3. Identify the dummy's final next, the old head's final successor, and the returned list. Why is a plain local assignment to head insufficient if the caller never receives the returned head?)
Core
Hint(1)
When , which node plays the role of
before?
Solution(3)
- 1
Identify the boundary nodes
beforeis the dummy andafteris the node with value 4. Reversing the segment makes . - 2
Read the final links
The dummy's final
nextis the node 9; the old head 7 now points to 4. Return the dummy'snext. - 3
Explain why the returned head is needed
If a function merely changes its local
headvariable, that assignment alone does not change a caller's separate head variable; the caller must use the returned head or explicitly pass a mutable reference to its head. The node links have changed, so keeping the old head would expose only the suffix starting at 7.
Quick check
(For with and , what are before, after and the returned chain?)
What is after when the segment reaches the end of the list?
Solution · Answer
before is the dummy and after is null, since the segment ends at the last node. Starting with prev=null, the loop produces , and the dummy's next is . Reversing the whole list is the special case , .
Errors to avoid
Common mistake
(Reconnecting the predecessor before the loop)
If before.next = prev is executed before the loop, prev still equals after. In the first practice question this sets , giving , and nodes , and are no longer reachable from the head. The predecessor must be reconnected only after the loop has built the reversed chain.
Sources: pointers and structs; lists.