Assume finite acyclic singly linked lists and sequential exclusive mutation.
Roadmap. Track node identity and the current positions after each operation. For validation, check every requested bound before rewriting any original link, then use the reversal invariant.
Checklist. A reversal reconnects both ends and may change the head. Invalid positions need an explicit policy. A validation pass must not dereference null. worst-case time and extra references assume pointer operations take constant time.
1. Two reversals use current positions
Exercise
(A list of distinct nodes is . First reverse positions 3 through 6. On the resulting list, reverse positions 2 through 4. Give the list after each operation and identify the final successor of node .)
Core
Hint(1)
Write down the list after the first reversal before choosing the nodes for the second.
Solution(3)
- 1
Reverse positions 3 through 6
The first segment is ; reversing it gives .
- 2
Read the second positions in the new list
Key step
Positions 2 through 4 in this new list are . The second operation does not refer back to the positions in the original list.
Because: The second operation acts on the list it receives.
- 3
Reverse them and read off the successor
Reversing gives . Therefore the final successor of is .
2. Reject invalid positions without changing the list
Exercise
(Extend the teaching algorithm to accept arbitrary integer positions on a finite acyclic list, including an empty list. If the positions are invalid, return error and leave every original next field unchanged. Describe validation precisely and give worst-case time and auxiliary space. Give the result for with .)
Core
Hint(1)
Do all checking before writing any original link.
Solution(5)
- 1
Reject impossible integers at once
If or , return
error. - 2
Walk to the predecessor with null checks
Set
dummy.next=headandbefore=&dummy. Repeat times: ifbefore.nextis null, returnerror; otherwise setbefore=before.next. - 3
Walk to the node after the segment with null checks
Set
after=before.nextand repeat times: ifafteris null, returnerror; otherwise advanceafter=after.next. If the list is empty, even fails here. - 4
Reverse only after validation succeeds
Key step
Run the teaching chapter's reversal loop with
first=before.nextand the computedafter, then assignbefore.nextand returndummy.next. No original link was written during validation, so every rejected input leaves the list unchanged; the dummy writes only a temporary record.Because: Validation reads links but never writes an original one.
- 5
Check the example and the cost
For with , validation reaches , advances through and , and finds null before completing four advances, so it returns
errorand is intact. For valid input, validation and reversal together use time and auxiliary references; for invalid input a check or a traversal stops at null, so the same bounds hold in a constant-time integer and pointer model. The acyclic-input assumption remains necessary.
Quick check
(Reverse positions through of a valid list, and then reverse the same positions through again. What is the final list?)
Which nodes occupy positions through after the first reversal?
Solution · Answer
The original list. The first reversal only permutes the nodes inside positions through , so those positions hold the same set of nodes. Reversing them again undoes the first reversal. For with , the lists are and then again.
Errors to avoid
Counterexample mode
Validating while rewriting
A tempting design reverses the segment and reports error when it meets null mid-loop. For with , take prev=null and start at . Iteration 1 sets B.next=null; iteration 2 sets C.next=B; at iteration 3 curr is null and the code returns error. The list is no longer : A.next is still , but B.next is null and points back to , so is unreachable from the head. The contract requires an unchanged list on error. The repair is to finish all checks before writing any original link.
Common mistake
(Reading the second operation's positions in the original list)
If the second operation is applied to positions 2 through 4 of the original list , one picks . In the list after the first operation, , these nodes sit at positions 2, 6 and 5, so they do not form a segment at all. The second operation must use the positions of the list it receives.
Sources: pointers and structs; lists.