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: previous, current, and next. We initialize previous to null and current to the head. In each iteration, we store the next node to avoid losing the rest of the list, then point current's next to previous. Finally, we shift all pointers forward. This ensures we traverse the list once with O(n) time complexity and O(1) space complexity. While a recursive solution exists, it risks a StackOverflowError on very long lists due to deep recursion, which contradicts Amazon's focus on robust, scalable systems. After implementing the loop, I would ensure the new tail points to null. For example, reversing 1->2->3 results in 3->2->1. I would verify this by tracing the pointer shifts manually during the interview to catch any off-by-one errors before finalizing the code.
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
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
Design a Set with $O(1)$ `insert`, `remove`, and `check`
Easy
CiscoFind the Celebrity (Graph)
Easy
UberConvert Binary Tree to Doubly Linked List in Place
Hard
MicrosoftFind K Closest Elements (Heaps)
Medium
MetaDesign a 'Trusted Buyer' Reputation Score for E-commerce
Medium
AmazonDesign a CDN Edge Caching Strategy
Medium
Amazon