Invertible Node Chain Reversal — Problem Statement & Solution Guide
Problem Description
You are provided with the head pointer of a singly linked list. Your task is to reverse the order of the nodes in-place. This operation must be performed by manipulating the 'next' pointers of the existing nodes, without allocating any new nodes or using auxiliary data structures (such as arrays or stacks) whose size grows with the length of the list.
The reversal must be stable in the sense that the relative order of the nodes is completely inverted. The node that was originally the tail of the list must become the new head, and the node that was originally the head must become the new tail with its 'next' pointer set to null.
Return the new head node of the reversed linked list. The solution must run in O(n) time complexity and O(1) space complexity, where n is the number of nodes in the list.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Invertible Node Chain Reversal"
WHY DOES IT MATTER?
In‑place reversal embodies the ‘two‑pointer’ manipulation pattern, a cornerstone for memory‑efficient algorithms on linear data structures. Mastery of this pattern signals a candidate’s ability to write low‑level, high‑performance code—a skill prized in systems, fintech, and high‑throughput services.
OPTIMIZATION CHALLENGE
The breakthrough is realizing that you only need to remember the immediate predecessor and successor of the current node. By updating the current node’s next pointer before moving forward, you avoid any need for auxiliary containers, collapsing the space complexity from O(n) to O(1).
REAL-WORLD CONNECTION
Think of a train reordering cars in a yard: each car (node) is detached and re‑attached to the front of a new train (reversed list) without building a new train from scratch. This mirrors how network packets or log entries might be reordered on the fly in distributed pipelines.
During the interview, write the three‑pointer loop on a whiteboard, then walk through a concrete example (e.g., 1→2→3) step‑by‑step. Explicitly state the invariant after each iteration; this demonstrates both correctness and deep understanding.
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 an iterative pointer manipulation technique that runs in linear time while using constant auxiliary space. The algorithm maintains three moving references—prev, curr, and next—so that each node's next pointer can be redirected to its predecessor without losing access to the remainder of the list. By advancing these pointers in a single pass, the list is transformed from head→…→tail into tail→…→head, preserving node identity and avoiding any allocation overhead.
Naïve approaches, such as copying node values into an auxiliary array or recursively traversing the list and unwinding the call stack, either violate the O(1) space constraint or risk stack overflow on massive inputs (e.g., millions of nodes). Recursion also incurs O(n) additional space due to call frames, which is unacceptable for hard‑level interview constraints where scalability is scrutinized. The optimal paradigm—iterative in‑place reversal—leverages the mutable nature of the next pointers, guaranteeing O(n) time and O(1) extra space regardless of list length.
The theoretical underpinning rests on the invariant that after processing k nodes, the sub‑list consisting of those k nodes is correctly reversed and detached from the untouched suffix. Maintaining this invariant through each iteration ensures correctness and provides a clean proof technique: induction on the number of processed nodes. This reasoning also clarifies why the algorithm cannot be simplified further without breaking the constant‑space guarantee.
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, curr, next). At each step, set curr.next = prev, then advance prev and curr. After the loop, prev points to the new head. The algorithm runs in O(n) time and O(1) extra space.
Q2Why is the recursive reversal of a linked list generally discouraged in a production interview setting?
Recursive reversal uses the call stack to store state, leading to O(n) auxiliary space and a risk of stack overflow for large lists. Interviewers expect an iterative solution that guarantees O(1) space and demonstrates explicit pointer control.
Q3Given a linked list where each node also has a random pointer, can you reverse the list while preserving the random pointers without extra space?
Yes. First reverse the next pointers using the standard in‑place method. Since random pointers reference nodes, they remain valid after reversal; no additional work is needed unless the problem explicitly requires re‑linking random pointers based on new order.
Examples
Input
head = [1, 2, 3, 4, 5]
Output
[5, 4, 3, 2, 1]
Explanation: Initial state: 1 -> 2 -> 3 -> 4 -> 5 -> null. Step 1: Reverse pointers for the first two nodes. 2 -> 1 -> null. Current head is 2. Step 2: Reverse pointers for the next node. 3 -> 2 -> 1 -> null. Current head is 3. Step 3: Reverse pointers for the next node. 4 -> 3 -> 2 -> 1 -> null. Current head is 4. Step 4: Reverse pointers for the last node. 5 -> 4 -> 3 -> 2 -> 1 -> null. Current head is 5. Final state: 5 -> 4 -> 3 -> 2 -> 1 -> null. Return node with value 5.
Input
head = [7, 12, 9]
Output
[9, 12, 7]
Explanation: Initial state: 7 -> 12 -> 9 -> null. Step 1: Reverse pointers for 7 and 12. 12 -> 7 -> null. Current head is 12. Step 2: Reverse pointers for 9. 9 -> 12 -> 7 -> null. Current head is 9. Final state: 9 -> 12 -> 7 -> null. Return node with value 9.
Input
head = [42]
Output
[42]
Explanation: Initial state: 42 -> null. Since there is only one node, reversing the list results in the same structure. Final state: 42 -> null. Return node with value 42.
Input
head = []
Output
[]
Explanation: The input list is empty. There are no nodes to reverse. Return null.
Constraints
- The number of nodes in the list is in the range [0, 5 * 10^4].
- -500 <= Node.val <= 500
- The list is guaranteed to be valid and acyclic.
Optimal Approach & Strategy
Iteratively rewire the next pointers using three pointers (prev, curr, next) in a single pass, achieving O(n) time and O(1) auxiliary space.
Brute Force Approach
Copy all node values into an array, reverse the array, then rewrite the values back into the list, which uses O(n) extra space.
Verified Code Solutions
function reverseList(head) {
let prev = null;
let curr = head;
let next = null;
while (curr !== null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
ListNode* next = nullptr;
while (curr != nullptr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
ListNode next = null;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}def reverseList(head):
prev = None
curr = head
next = None
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prevfunction reverseList(head) {
let prev = null;
let curr = head;
let next = null;
while (curr !== null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}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.