Reverse Linked List
You are a Fresher on-call. A production issue might involve Reverse Linked List. How do you diagnose and mitigate?
Answers use simple, clear English.
Quick interview answer
Mitigate first, then root-cause. Check symptoms against: Losing reference to next before rewiring; returning wrong node (old head vs new head)..
Detailed answer
Mitigate first, then root-cause. Check symptoms against: Losing reference to next before rewiring; returning wrong node (old head vs new head).. Validate with: Draw three pointers; return prev as new head after loop.. Context: Iterative: prev=None, curr=head; save next, point curr.next=prev, advance. Recursive variant uses head as new tail after reversing rest. Core: Iterative: prev=None, curr=head; save next, point curr.next=prev, advance. Recursive variant uses head as new tail after reversing rest. Real-time example: Undo stack in a text editor implemented as singly linked list needs in-place reversal for replay. Pros: O(n)/O(1) iterative; tests pointer discipline fundamentals. Cons: Recursive version O(n) stack; doubly linked needs both pointer updates. Common mistakes: Losing reference to next before rewiring; returning wrong node (old head vs new head). Best practices: Draw three pointers; return prev as new head after loop. Audience level: Fresher.
Full explanation
Iterative: prev=None, curr=head; save next, point curr.next=prev, advance. Recursive variant uses head as new tail after reversing rest.
Real example & use case
Undo stack in a text editor implemented as singly linked list needs in-place reversal for replay.
Pros & cons
Pros: O(n)/O(1) iterative; tests pointer discipline fundamentals. Cons: Recursive version O(n) stack; doubly linked needs both pointer updates.
Common mistakes
Losing reference to next before rewiring; returning wrong node (old head vs new head).
Best practices
Draw three pointers; return prev as new head after loop.
Follow-up questions
- How would you test Reverse Linked List?
- What metrics prove Reverse Linked List is healthy in prod?
- How does Reverse Linked List change at 10× traffic?