Reverse a list with a stack
Updated
Walk the list pushing node values (or node pointers), then pop to rebuild. Values-only copy makes new nodes. Pointers-only reverse still needs rewiring. A stack of nodes can relink in pop order.
What to focus on
4→1→9→1 pushed as values becomes pops 1,9,1,4. One node stays one node. This uses O(n) extra. In-place three-pointer reverse uses O(1) extra and is a different skill.
Worked examples
four
a = [4, 1, 9, 1]- push while walking
- pop to 1,9,1,4
Result: 1 → 9 → 1 → 4 → null
one
a = [7]- same node value
Result: 7 → null
two
a = [4, 1]- push 4,1
- pop 1,4
Result: 1 → 4 → null
Try it
Write reverseWithStack(head). head is the first node of the list. node.next is the next node, or null at the end. Walk onto a stack and rebuild from pops. This uses O(n) extra, unlike in-place reverse. Walk [4, 1, 9, 1] and rebuild 1 → 9 → 1 → 4. Also [7] and [4, 1].
The list is non-empty. Values are integers.