Why does reversing a singly linked list run in O(n) time and O(1) space, and what state do you have to track to avoid losing the rest of the list?

technical-conceptual · Mid level · software-engineering

What the interviewer is really asking

Probes whether the candidate can drive the iterative pointer-reversal in place, name the three-pointer state it requires, and contrast it with the recursive version's space cost rather than reciting a memorized template.

What to say

• Walk the list once, and at each node flip its next pointer to point backward. The trap is that flipping next destroys your link to the rest of the list, so you must capture node.next into a temporary before you overwrite it.
• You carry three references: prev (starts null), curr (the node you're rewiring), and a saved next. Each step: save next = curr.next, set curr.next = prev, advance prev = curr, then curr = next. When curr is null, prev is the new head. That's one pass, O(n) time, and only a constant number of pointers, so O(1) extra space.
• Contrast the recursive version: it's the same O(n) time but O(n) space because each frame sits on the call stack until the base case, which can overflow on a long list. The iterative in-place version is what you'd ship for an unbounded-length list.

What to avoid

• Overwrite curr.next = prev before saving the original next, which strands the unvisited remainder of the list and leaves you with a length-one result.
• Claim the recursive solution is also O(1) space, ignoring that every unreturned frame holds a node on the call stack.
• Build a brand-new list by copying every node's value into a fresh reversed list and call it in-place, when it actually costs O(n) extra space.

Example answers

Strong: I needed to reverse an in-memory event chain without allocating, so I used the three-pointer iterative walk: save next, point curr back at prev, slide both forward. One pass, no allocation, and I verified the new head was the old tail. I picked iterative specifically because the chains could be very long and recursion would have risked a stack overflow.

Weak: I'd loop through and set each node's next to the previous node — point it backward and move on.