ASAPUtils
The signal
The list links must change in place and only O(1) extra space is needed. This is the base pointer operation behind sublist reversal, k-group reversal, palindrome checks, and Reorder List.
The invariant
prevheads a correctly reversed prefix;currheads the untouched suffix; together they still reach every original node.
The only dangerous moment is changing curr.next. Preserve its old target first.
Optimal solution
ListNode* reverseList(ListNode* head) {
ListNode *prev = nullptr, *curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
function reverseList(head) {
let prev = null, curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
Why it works
Each iteration moves exactly one node across the boundary. Setting curr.next = prev makes it the
new front of the reversed prefix. Advancing curr to the saved successor preserves access to every
unprocessed node. When the suffix is empty, the prefix is the whole reversed list.
Complexity
Every node is visited once: O(n) time. Three node references are used regardless of input size: O(1) auxiliary space.
Traps
- Reversing before saving
nextand losing the rest of the list. - Returning
head; the original head is now the tail. - Copying values into an array, which avoids the actual pointer requirement and uses O(n) space.
- Writing a recursive solution without accounting for its O(n) call stack.
Blank re-solve prompt
Draw four named nodes. After every iteration, write the identities held by prev, curr, and next, then implement the loop in both languages without looking at the template.