Reverse a Linked List
Prompt
We store each user's recent activity as a singly linked list, newest event at the head. Product wants to render it oldest-first. Walk me through how you'd reverse that list in place.
How this round runs
I'm not telling you up front whether recursion is allowed or how long these lists get — clarify that before you commit to an approach, and expect a twist once you have something working.
Model answer
Clarify first: can I mutate the existing nodes in place, or do I need a fresh list? How long can these lists get — are we at risk of a deep call stack? Is the input ever null or a single node?
The core idea is rewiring each next pointer to point backward. Brute force
would be to copy values into an array and rebuild — O(n) time but O(n) extra
space and it sidesteps the actual pointer work. Better: an in-place iterative
walk with three pointers — prev, current, and a saved next so we don't
lose the rest of the list when we flip a link. That's O(n) time and O(1)
space.
function reverse(head) {
let prev = null;
let current = head;
while (current !== null) {
const next = current.next; // save before we clobber it
current.next = prev; // flip the link backward
prev = current; // advance prev
current = next; // advance current
}
return prev; // old tail is the new head
}
Dry-run on 1 -> 2 -> 3: save next=2, point 1 back to null, prev=1, current=2;
save next=3, point 2 back to 1, prev=2, current=3; save next=null, point 3 back
to 2, prev=3, current=null; loop ends, return 3. List is now 3 -> 2 -> 1.
The recursive form recurses to the tail, then on the way back sets
head.next.next = head and head.next = null. Clean to read, but it's O(n)
stack space and risks a stack overflow on a very long activity log — which is
why I'd default to iterative here.
- Asked whether in-place mutation is allowed and how long the lists get
- Saved the next pointer before reversing, and said why that order matters
- Stated O(n) time and O(1) space for the iterative approach
- Dry-ran the pointer moves on a 3-node list
- Now do it recursively → tail base case, rewire on the unwind, note the O(n) stack cost
- Reverse only the sub-range between positions m and n → splice out the segment, reverse it, stitch the boundaries back