Reverse a Linked List — Problem Statement & Solution Guide
Problem Description
You are given the head pointer of a singly linked list. The objective is to invert the sequence of nodes by modifying the internal next references of the existing nodes. This operation must be performed in-place, meaning no new node objects should be instantiated during the process. The node that was originally the tail of the list must become the new head, and the original head node must become the new tail with its next pointer set to null.
The reversal logic requires carefully managing three pointers to prevent losing track of the remaining unprocessed nodes. As you traverse the list, you must redirect the next pointer of the current node to point to the previous node in the sequence. After updating the pointer, you must advance your traversal pointers to the next node in the original list before the link is broken.
Return the head node of the reversed linked list. If the input list is empty or contains only a single node, return the same head node as the list remains unchanged.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Reverse a Linked List"
WHY DOES IT MATTER?
In‑place reversal teaches disciplined pointer handling, a skill essential for any low‑level data‑structure manipulation, memory‑critical systems, and interview scenarios where space constraints are explicit.
OPTIMIZATION CHALLENGE
The key insight is to reverse the direction of each edge *before* losing access to the rest of the list, which is achieved by temporarily storing the next node. This single‑pass, constant‑space trick eliminates the need for auxiliary containers or recursion.
REAL-WORLD CONNECTION
Think of a conveyor belt where each package points to the next. Reversing the belt without adding new packages mirrors re‑routing network packets in a reverse path without allocating extra buffers, a common pattern in distributed systems and networking stacks.
During an interview, write the three‑pointer loop first, then walk through a short example on the whiteboard to prove correctness before coding; this demonstrates both clarity of thought and attention to edge cases.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
Reversing a singly linked list in-place is a classic example of pointer manipulation that showcases the power of iterative state transitions. The naive mental model—traversing the list and appending nodes to a new list—requires O(n) extra space, which violates the in‑place constraint and can cause memory pressure on large inputs. The optimal algorithm maintains three pointers (prev, curr, next) and iteratively redirects each node's next reference to its predecessor, effectively walking the list while flipping the direction of edges. This approach runs in linear time because each node is visited exactly once, and it uses constant auxiliary space, making it scalable for lists with millions of elements.
The underlying paradigm is a deterministic state machine: at each iteration the algorithm transitions from one configuration (prev, curr) to the next by storing the upcoming node (next) before mutating curr.next. This ordering is crucial; without preserving the original next reference, the list would become partially disconnected, leading to data loss. The technique also generalizes to other problems such as reversing sub‑lists, rotating lists, and even in-place tree transformations, reinforcing its centrality in linked‑structure manipulation.
Naive recursive reversal, while elegant, incurs O(n) call‑stack depth, which can cause stack overflow on deep lists and violates the strict O(1) auxiliary space requirement for many interview settings. The iterative method sidesteps this by using explicit variables, guaranteeing both safety and performance across all input sizes.
Interview Questions on This Problem
Q1How would you reverse a singly linked list in-place and what is its time and space complexity?
Iterate through the list with three pointers: prev (initially null), curr (head), and next (curr.next). In each step, store next, set curr.next = prev, then move prev to curr and curr to next. After the loop, prev is the new head. This runs in O(n) time and O(1) extra space.
Q2Can you reverse a linked list between positions m and n in a single pass? Explain the approach.
Yes. First, traverse to the node just before position m, keeping a pointer pre. Then reverse the sub‑list from m to n using the standard three‑pointer technique, while keeping a pointer to the tail of the reversed segment. Finally, reconnect pre.next to the new head of the reversed segment and the tail's next to the node after n. This maintains O(n) time and O(1) space.
Q3Why might a recursive solution for reversing a linked list be disfavored in production code, especially for very large lists?
Recursive reversal uses the call stack to store state, leading to O(n) additional space and a risk of stack overflow when n exceeds the language's recursion limit. In production, this can cause crashes or degraded performance, so an iterative O(1) space solution is preferred.
Examples
Input
head = [4, 12, 7, 9, 3]
Output
[3, 9, 7, 12, 4]
Explanation: Initial state: 4 -> 12 -> 7 -> 9 -> 3 -> null. Step 1: prev=null, curr=4. Set curr.next (4.next) to prev (null). Advance prev to 4, curr to 12. List: null <- 4, 12 -> 7 -> 9 -> 3. Step 2: prev=4, curr=12. Set curr.next (12.next) to prev (4). Advance prev to 12, curr to 7. List: null <- 4 <- 12, 7 -> 9 -> 3. Step 3: prev=12, curr=7. Set curr.next (7.next) to prev (12). Advance prev to 7, curr to 9. List: null <- 4 <- 12 <- 7, 9 -> 3. Step 4: prev=7, curr=9. Set curr.next (9.next) to prev (7). Advance prev to 9, curr to 3. List: null <- 4 <- 12 <- 7 <- 9, 3. Step 5: prev=9, curr=3. Set curr.next (3.next) to prev (9). Advance prev to 3, curr to null. List: null <- 4 <- 12 <- 7 <- 9 <- 3. Final head is prev (3). Result: 3 -> 9 -> 7 -> 12 -> 4 -> null.
Input
head = [100, 200]
Output
[200, 100]
Explanation: Initial state: 100 -> 200 -> null. Step 1: prev=null, curr=100. Set 100.next to null. Advance prev to 100, curr to 200. Step 2: prev=100, curr=200. Set 200.next to 100. Advance prev to 200, curr to null. Final head is prev (200). Result: 200 -> 100 -> null.
Input
head = [55]
Output
[55]
Explanation: Initial state: 55 -> null. Step 1: prev=null, curr=55. Set 55.next to null. Advance prev to 55, curr to null. Final head is prev (55). Result: 55 -> null.
Input
head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Output
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Explanation: The list is reversed iteratively. Each node's next pointer is updated to point to its predecessor. The final head becomes the original tail (10), and the original head (1) becomes the tail with next=null.
Constraints
- The number of nodes in the list is in the range [0, 5 * 10^4].
- -1000 <= Node.val <= 1000
- The list is guaranteed to be a valid singly linked list with no cycles.
- The solution must run in O(n) time complexity.
- The solution must use O(1) extra space complexity.
Optimal Approach & Strategy
Iteratively reverse the next pointers in a single pass using three pointers, achieving O(n) time and O(1) auxiliary space.
Brute Force Approach
Create a new linked list and prepend each visited node, which uses O(n) extra space and requires two passes—one to traverse and one to rebuild.
Verified Code Solutions
function reverseList(head) {
let prev = null;
let curr = head;
while (curr !== null) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
function reverseList(head) {
let prev = null;
let curr = head;
while (curr !== null) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.