Reverse a Linked List
Given the head of a singly linked list, reverse the list and return the reversed head. Implement both iterative and recursive solutions.
Why Interviewers Ask This
Amazon asks this to evaluate your grasp of pointer manipulation and memory management fundamentals. They specifically test if you can handle edge cases like null inputs or single-node lists without crashing. The question also reveals your ability to choose between iterative and recursive approaches based on stack depth constraints, a critical skill for scalable backend systems.
How to Answer This Question
1. Clarify the input: Ask about empty lists or single nodes immediately to show attention to detail. 2. Visualize first: Draw the list nodes on a whiteboard to explain the 'next' pointer changes before writing code. 3. Propose Iterative: Suggest the three-pointer approach (prev, curr, next) as it is O(1) space and safer for Amazon's production environments. 4. Discuss Recursive: Briefly mention the recursive solution but highlight its O(n) stack space risk for large datasets. 5. Dry Run: Walk through your code with a sample input [1, 2, 3] step-by-step to verify logic. This structured method demonstrates the 'Dive Deep' leadership principle by showing thoroughness.
Key Points to Cover
- Explicitly handling edge cases like null heads or single nodes
- Choosing the iterative approach for optimal space complexity
- Demonstrating clear pointer manipulation logic without getting lost
- Acknowledging the recursion stack depth limitation for large inputs
- Walking through a concrete dry run to validate correctness
Sample Answer
To reverse a singly linked list, I would first validate the input. If the head is null or contains only one node, we simply return it as-is. For the main logic, I prefer an iterative approach using three pointers: previo…
Common Mistakes to Avoid
- Forgetting to set the original head's next pointer to null, creating a cycle
- Losing track of the remaining list by overwriting the next pointer too early
- Implementing recursion without considering potential stack overflow issues
- Skipping the edge case check for an empty input list entirely
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.