Reverse Linked List
Implement or sketch code for Reverse Linked List. Explain the logic, complexity, and pros/cons of this approach.
Answers use simple, clear English.
Quick interview answer
Logic: Iterative: prev=None, curr=head; save next, point curr.next=prev, advance. Recursive variant uses head as new tail after reversing rest.
Detailed answer
Logic: Iterative: prev=None, curr=head; save next, point curr.next=prev, advance. Recursive variant uses head as new tail after reversing rest. Complexity notes included in code section when present. Pros: O(n)/O(1) iterative; tests pointer discipline fundamentals. Cons: Recursive version O(n) stack; doubly linked needs both pointer updates. 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: Senior.
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.
Code example
class ListNode:
def __init__(self, val: int = 0, nxt=None):
self.val, self.next = val, nxt
def reverse_list(head: ListNode | None) -> ListNode | None:
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
return prevPractice code · python (view only · no execution)
class ListNode:
def __init__(self, val: int = 0, nxt=None):
self.val, self.next = val, nxt
def reverse_list(head: ListNode | None) -> ListNode | None:
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
return prevCommon 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?