Reverse Linked List: Iterative and Recursive Solutions
The Prompt
Given the `head` of a singly linked list, reverse the list, and return the reversed list.
Understanding the Problem
A singly linked list only knows how to go forward: each node stores one next pointer. Reversing the list means every arrow must end up pointing the opposite way — but the moment you flip a node’s next pointer, you lose your only road to the rest of the list.
That is the whole difficulty. The fix is bookkeeping: before flipping curr.next, stash curr.next in a temporary next variable. Three pointers — prev (already-reversed part), curr (node being flipped), next (unvisited part) — walk the list together in one pass.
The Interview Flow
Interviewer
How would you reverse a singly linked list?
Candidate
There are two common ways: iteratively and recursively. The iterative approach is generally more space-efficient.
Interviewer
Let's talk about the iterative approach first.
Candidate
I would use three pointers: `prev`, `current`, and `next`. I'd initialize `prev` to null and `current` to the head. I'd then iterate through the list. In each step, I first store the next node (`next = current.next`), then I reverse the pointer of the current node (`current.next = prev`), and finally, I move my `prev` and `current` pointers one step forward (`prev = current`, `current = next`).
Interviewer
What is the state of the pointers when the loop finishes?
Candidate
When the loop finishes, `current` will be null, and `prev` will be pointing to the new head of the reversed list. So I just need to return `prev`.
Interviewer
That's correct. Now, how would you approach it recursively?
Candidate
For the recursive solution, the base case is an empty list or a list with one node, in which case I return the head. Otherwise, I recursively call the function on `head.next`. This will reverse the rest of the list and return the new head. Let's say the new head is `newHead`. Now, I need to attach the original `head` to the end of this reversed list. I can do this by setting `head.next.next = head` and `head.next = null`. Finally, I return `newHead`.
Interviewer
Both approaches are solid. Please implement the iterative one.
Why do three pointers reverse the list in one pass?
The invariant: at every step, everything left of curr is fully reversed and prev points at its head, while everything from curr onward is still in original order. Each loop iteration flips exactly one arrow (curr.next = prev) and then shifts both prev and curr one node right — so the invariant survives, one node at a time.
When curr falls off the end (null), the "reversed" region is the entire list and prev is its new head. Every node is visited once and only a constant number of pointers exist, so it is O(n) time and O(1) space — strictly better than the recursive version, which spends O(n) stack space to do the same flips.
Iterative Solution with Three Pointers
- Initialize two pointers: `prev` to `null` and `curr` to `head`.
- Loop as long as `curr` is not `null`.
- Inside the loop, store the next node before you change any pointers: `nextNode = curr.next`.
- Reverse the pointer of the current node: `curr.next = prev`.
- Move the pointers one step forward for the next iteration: `prev = curr` and `curr = nextNode`.
- When the loop terminates, `curr` will be `null`, and `prev` will be the new head of the reversed list.
- Return `prev`.
Try it yourself
Write your solution and run it against 3 test cases.
Lists are given as ListNode chains; test inputs/outputs display as arrays.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}Explanation
Reverse the list 1 → 2 → 3 → 4 and watch the arrows flip one at a time.
1Start: prev = null, curr = head (1). Nothing is reversed yet; every arrow still points forward.
2Iteration 1: save next = 2, flip 1.next to prev (null), then advance: prev = 1, curr = 2. The reversed region is just [1].
3Iteration 2: flip 2.next to point at 1. Now 2 → 1 → null is reversed while 3 → 4 is untouched — the invariant holds.
4After flipping 3 and 4, curr = null and the loop ends. prev points at 4, the head of the fully reversed list — return prev.
Complexity Analysis
TIME
O(n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.