Before changing cur.next, save nxt=cur.next. After rewiring, update the boundaries of processed and unprocessed chains. A dummy turns head operations into ordinary successor operations.
Recognition signals
The input is a singly linked list and mutation should be in place.
The operation changes node order or removes nodes.
Random access is unavailable; progress follows next.
The head may change and creates many boundary branches.
False friends
Signal
Why it is different
Read-only list traversal
If values are only inspected, no rewiring is needed; a simple or fast-slow traversal suffices.
Frequent index access
Linked storage is poor for random locations; conversion to an array may fit better.
Core invariant
prev bounds the correctly processed chain and cur is the first unprocessed node; every original node belongs to exactly one side and remains reachable.
State, transition, and processing order
Item
Definition
State
Optional dummy, prev, cur, nxt, and operation-specific segment heads or tails.
Transition
Save nxt, redirect cur.next to its new destination, then advance prev=cur and cur=nxt.
Frontier / order
The single boundary between a rewired processed prefix and an untouched original suffix.
Python skeleton
def reverse_list(head):
prev, cur = None, head
while cur is not None:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
Correctness sketch
Saving nxt preserves reachability of the unprocessed suffix before cur.next is overwritten.
Each round moves cur from the original suffix to the front of the correctly reversed prefix, preserving the partition.
When cur is None, every node is in the reversed prefix, prev is its head, and every next edge has the desired direction.
Complexity
Time
Space
Parameters
O(n)
O(1)
n is the number of processed nodes; each next pointer changes a constant number of times.
Edge cases
An empty list returns None.
A singleton continues to point to None.
A dummy avoids a special branch when deleting the head.
If cycles are possible, a plain while cur loop needs a stated acyclic precondition or prior detection.
Error patterns
Pattern
Why it fails / fix
Overwriting next before saving it
The unprocessed suffix becomes permanently lost.
Returning the old head
After full reversal, the new head is prev.
Not reconnecting a reversed segment
Local reversal requires both the predecessor before the segment and successor after it.
Selection and exclusion rules
When the head may change, draw a dummy first.
Before every next assignment, write nxt=cur.next.
For complex reorderings, label each segment head and tail before connecting them.