Reverse a Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
Why Interviewers Ask This
Google uses this classic problem to assess a candidate's mastery of pointer manipulation and memory management fundamentals. It evaluates whether you can traverse a data structure without auxiliary space, handle edge cases like null pointers or single-node lists, and think logically about state transitions in an iterative or recursive manner.
How to Answer This Question
1. Clarify the constraints immediately: ask if the list is singly linked, what happens with an empty input, and whether recursion is allowed given Google's focus on stack depth. 2. Propose the optimal iterative approach first to demonstrate efficiency awareness, explaining that it uses O(1) space compared to O(n) for recursion. 3. Walk through the logic using three pointers: 'previous', 'current', and 'next'. Explicitly describe how 'current.next' must be updated to point to 'previous' before moving forward. 4. Trace a small example manually (e.g., 1->2->3) on a whiteboard to visualize the pointer swaps step-by-step. 5. Analyze time and space complexity aloud, confirming O(n) time and O(1) space, then offer the recursive alternative as a secondary thought if asked.
Key Points to Cover
- Explicitly handling null and single-node edge cases before writing code
- Choosing the iterative solution to demonstrate O(1) space complexity awareness
- Using a clear three-pointer strategy (prev, curr, next) to manage state
- Manually tracing the pointer changes with a concrete example during explanation
- Verifying time and space complexity after presenting the solution
Sample Answer
To reverse a singly linked list efficiently, I would use an iterative approach with constant space complexity. First, I need to handle edge cases where the head is null or contains only one node, returning it immediately…
Common Mistakes to Avoid
- Forgetting to update the next pointer before changing the current node's reference, causing the list to break
- Failing to check for an empty list or single-node list at the very beginning
- Attempting to swap values instead of swapping node references, which is incorrect for linked list structures
- Not mentioning space complexity or choosing a recursive solution without discussing stack overflow risks
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.