Reverse Linked List
Asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Walmart
Problem
Given the head of a singly linked list, reverse it and return the reversed list. This is one of the most fundamental linked list problems and a building block for many harder questions.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Meta | Easy | View all Meta questions → |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Apple | Easy | View all Apple questions → |
| Uber | Easy | View all Uber questions → |
| Walmart | Easy | View all Walmart questions → |
How to Think About It
Use three pointers: prev (starts null), current (starts at head), next (temporary). At each step, reverse the current node's pointer to point backward.
The four-step dance at each node: (1) save next = current.next, (2) current.next = prev, (3) prev = current, (4) current = next.
When current becomes null, prev is the new head. The old head is now the tail (its next is null).
Visual walkthrough for 1→2→3→null:
Start: prev=null, curr=1
Step 1: next=2, 1.next=null, prev=1, curr=2. List: 1→null
Step 2: next=3, 2.next=1, prev=2, curr=3. List: 2→1→null
Step 3: next=null, 3.next=2, prev=3, curr=null. List: 3→2→1→null
curr=null → return prev=3. Result: 3→2→1→null
Recursive approach: reverseList(head.next) does the heavy lifting. Then head.next.next = head, head.next = null. Elegant but O(n) stack space.
Optimal Approach
Iterative:
Step 1: Initialize prev = null, curr = head.
Step 2: While curr is not null:
- Save next = curr.next
- curr.next = prev (reverse the pointer)
- prev = curr (move prev forward)
- curr = next (move curr forward)
Step 3: Return prev (the new head).
The key insight: you're reversing one pointer at a time. By the time curr reaches null, every pointer has been flipped.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Not handling the edge case of an empty list or a single node. Return null or the node itself.
Losing track of the next node before reassigning pointers. Save next = current.next before setting current.next = prev.
Confusing iterative and recursive approaches. The iterative approach uses three pointers (prev, current, next). The recursive approach is elegant but uses O(n) stack space.
Forgetting to update the head. After the loop, the new head is prev (the last node you processed).
Trying to reverse by creating new nodes instead of re-pointing existing ones. The problem expects in-place reversal by changing pointers, not building a new list with copied values.
Solution Code
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prevFrequently Asked Questions
What is the Reverse Linked List problem?
Given the head of a singly linked list, reverse it and return the reversed list. This is one of the most fundamental linked list problems and a building block for many harder questions.
How do you solve Reverse Linked List?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Reverse Linked List?
Reverse Linked List is asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Walmart. It is a easy difficulty problem.
What are common mistakes on Reverse Linked List?
- Not handling the edge case of an empty list or a single node. Return `null` or the node itself.
- Losing track of the next node before reassigning pointers. Save next = current.next before setting current.next = prev.
- Confusing iterative and recursive approaches. The iterative approach uses three pointers (prev, current, next). The recursive approach is elegant but uses `O(n)` stack space.
- Forgetting to update the head. After the loop, the new head is prev (the last node you processed).
- Trying to reverse by creating new nodes instead of re-pointing existing ones. The problem expects in-place reversal by changing pointers, not building a new list with copied values.