MicrosoftData StructuresMedium
Reverse a Linked List
Linked ListAlgorithmsRecursion
Question
Given the head of a singly linked list, reverse the list and return the reversed list.
Interview Answer
Use three pointers (`prev`, `current`, `next`) and iterate through the list once, reversing each node’s `next` pointer. This produces O(n) time with O(1) extra space and avoids recursion stack overhead, making it the preferred interview solution.
Explanation
For each node, store next node, reverse current pointer, then advance pointers. Recursive solution is elegant but uses call stack O(n). Interview-preferred answer is usually iterative due to constant space.
Key Points
- Maintain previous/current/next pointers safely
- Reverse direction of links in-place
- Handle edge cases: empty list and single node
- Iterative approach is optimal for space
Common Mistakes
- Losing the next node reference before reversing pointer
- Returning original head instead of new head
- Forgetting null and one-node edge cases
Likely Follow-Up Questions
- How would you reverse a linked list between positions m and n?
- How do you detect a cycle before reversing?
- How would you reverse in groups of k nodes?
Interview Timing
Target speaking time: about 4 minutes.