What is the space complexity of reversing a singly linked list recursively (excluding input storage)?

• A. O(1) space
• B. O(n) space due to the call stack
• C. O(n) extra heap usage
• D. O(log n) space

Answer: (B)

Understanding how recursion affects space usage is key here. When reversing a singly linked list recursively, each recursive call pushes a new frame onto the call stack. You keep calling on the next node until you reach the end, so for a list with n nodes the maximum stack depth is n. During the unwind, those frames are popped, but at their deepest point you needed n frames. That means the extra memory used, aside from the nodes themselves, grows linearly with the number of nodes. So the space complexity is O(n) due to the call stack.

This is not O(1) because there’s no constant amount of extra space independent of n; it’s not O(log n) because the depth is not logarithmic but linear; and it’s not extra heap usage since no additional data structures are allocated beyond the stack frames. If you reversed iteratively, you could achieve O(1) auxiliary space, but the recursive approach inherently uses a linear call stack.