Approach Summary
Iterative: maintain prev and curr. At each step, save next, point curr.next to prev, advance both. Recursive: reverse rest, link back.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Iterative Pointer Reversal (Optimal) | O(n) | O(1) | Reverse links in-place using three pointers (prev, curr, next) in O(1) space. |
| 2 Approach 2: Recursive Reversal | O(n) | O(n) call stack | Recursively reverse the tail of the list and link head.next.next back to head. |
Step 1: Baseline
Approach 1: Iterative Pointer Reversal (Optimal)
Time: O(n)
Space: O(1)
Initialize prev as null and curr as head. As curr traverses the list, capture curr.next in next. Redirect curr.next backwards to prev. Move prev forward to curr, and advance curr to next. When curr reaches null, prev is the new head of the reversed list.
Approach 1: Iterative Pointer Reversal (Optimal) Implementation
Approach 1: Iterative Pointer Reversal (Optimal)
class Solution {
public ListNode reverseList(ListNode head) {
ListNode currNode = head;
ListNode prevNode = null;
ListNode nextNode = head;
while (currNode != null) {
nextNode = currNode.next;
currNode.next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
return prevNode;
}
}class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* Current_Node = head;
ListNode* Prev_Node = NULL;
ListNode* Next_Node = head;
while (Current_Node != NULL) {
Next_Node = Current_Node->next;
Current_Node->next = Prev_Node;
Prev_Node = Current_Node;
Current_Node = Next_Node;
}
return Prev_Node;
}
};class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prevfunction reverseList(head) {
let prev = null, curr = head;
while (curr !== null) {
const nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
return prev;
} Step 2: Most Optimized
Approach 2: Recursive Reversal
Time: O(n)
Space: O(n) call stack
Base case: if head is null or head.next is null, return head. Otherwise, recursively reverse head.next, obtaining newHead. Then point head.next.next = head and sever the old forward pointer with head.next = null. Return newHead.
Approach 2: Recursive Reversal Implementation
Approach 2: Recursive Reversal
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
};class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
new_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return new_headfunction reverseList(head) {
if (!head || !head.next) return head;
const newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}Edge Cases to Watch
- Empty list (head is null; returns null)
- Single node list (returns the head unchanged)
- Two-node list (e.g. 1 -> 2 becomes 2 -> 1)
- Long list up to 5000 nodes
Algorithmic Pattern
View Pattern Guide →
Master the Linked List Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Linked List pattern.
Framework: Linked List • Interview Prep: Tested at FAANG •
Explore all Linked List problems & invariants →
How to Recognize This Pattern
- Reverse linked list in-place
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Linked List Recursion
Frequently Asked Questions
What is the optimal time and space complexity for Reverse Linked List?
The optimal solution for Reverse Linked List achieves O(n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n) because every node is visited exactly once. Space complexity is O(1) for the iterative pointer manipulation and O(n) for the recursive call stack.
How do I identify that Reverse Linked List requires the Linked List pattern?
In technical interviews, look for key problem signals: Reverse linked list in-place. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Linked List strategy.
What critical edge cases must be handled in Reverse Linked List?
Essential edge cases to verify include: Empty list (head is null; returns null); Single node list (returns the head unchanged); Two-node list (e.g. 1 -> 2 becomes 2 -> 1); Long list up to 5000 nodes. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Reverse Linked List?
Reverse Linked List is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Microsoft, Apple.