Reverse Linked List
Last Updated: March 29, 2026
Understanding the Problem
Reversing a linked list means flipping the direction of every pointer. In the original list, each node points to the next one: 1->2->3->4->5->null. After reversal, each node should point to the previous one: 5->4->3->2->1->null. The old tail becomes the new head.
The challenge is that singly linked lists only have forward pointers. You can't look backward. So to reverse a node's pointer, you need to have already saved a reference to the previous node before you move forward. If you don't, you lose track of where to point.
This is one of the most fundamental linked list operations. It shows up as a building block in dozens of other problems (reverse nodes in k-group, palindrome linked list, reorder list), so understanding it deeply pays off.
Key Constraints:
0 <= n <= 5000→ The list can be empty (0 nodes) or have up to 5,000 nodes. We need to handle the empty list edge case. With n up to 5,000, even O(n^2) would work, but O(n) is the natural fit since we need to visit every node.-5000 <= Node.val <= 5000→ Node values can be negative. This doesn't affect the algorithm, but it's good to note that we're not making any assumptions about values.- Singly linked list → No backward pointers. This is the core constraint that makes reversal non-trivial.
Approach 1: Iterative (Three Pointers)
Intuition
The idea is straightforward: walk through the list one node at a time, and at each node, flip its next pointer to point backward instead of forward. To do this safely, we need three pointers:
prev-- the node we want the current node to point to (starts as null since the new tail should point to null)curr-- the node we're currently processingnext-- a temporary save ofcurr.nextbefore we overwrite it
Without saving next, the moment we set curr.next = prev, we lose our only reference to the rest of the list. That's the key insight: always save the forward link before breaking it.
Algorithm
- Initialize
prev = nullandcurr = head. - While
curris not null: - Save
next = curr.next(so we don't lose the rest of the list). - Reverse the pointer:
curr.next = prev. - Move
prevforward:prev = curr. - Move
currforward:curr = next. - When
curris null,prevpoints to the last node we processed, which is the new head. Returnprev.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once. Each visit does a constant amount of work (save, reverse, advance).
- Space Complexity: O(1). We only use three pointer variables (
prev,curr,next) regardless of the list size.
This approach is already optimal in both time and space. O(n) time is required since we must touch every node, and O(1) space is as good as it gets.
The follow-up asks for a recursive solution. Can we express the reversal as a recursive subproblem: "reverse the rest of the list, then fix up the current node"?
Approach 2: Recursive
Intuition
Here's the recursive way to think about it: if we could somehow reverse everything after the current node, all we'd need to do is make the next node point back to the current node and set the current node's next to null.
For example, take the list 1->2->3->4->5. Suppose we've already reversed everything after node 1, giving us 1->2<-3<-4<-5. Node 1 still points to node 2, and node 2's next is null (it's the tail of the reversed sublist). We just need to set 2.next = 1 and 1.next = null, and the full list is reversed.
The base case is when we reach the last node (or null). A single node or empty list is already "reversed," so we just return it. The recursion unwinds from the tail back to the head, fixing one pointer at each level.
Interviewers love asking for both iterative and recursive solutions. The recursive approach shows you understand call stack mechanics and can think about problems in terms of subproblems.
Algorithm
- Base case: if
headis null orhead.nextis null, returnhead(a list of 0 or 1 nodes is already reversed). - Recursively reverse the sublist starting from
head.next. This returns the new head of the reversed sublist. - Fix the pointers:
head.next.next = head(make the next node point back to current). - Set
head.next = null(current node becomes the new tail of its portion). - Return the new head (which was returned by the recursive call).
Example Walkthrough:
Code
- Time Complexity: O(n). We make exactly n recursive calls, one per node. Each call does O(1) work.
- Space Complexity: O(n). The recursion stack holds n frames (one for each node). This is the main downside compared to the iterative approach.