Pattern: In-place Reversal of a LinkedList — Problem Statement & Solution Guide
Problem Description
Given the head node of a singly linked list, rearrange the list so that its nodes appear in reverse order. The transformation must be performed in-place, i.e., only a constant amount of extra memory may be used besides the variables needed for traversal. Return the new head of the reversed list. Each node contains an integer value and a reference to the next node (or null for the last node). The input list may contain from one up to a hundred thousand nodes, and node values can be any 32‑bit signed integer.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Pattern: In-place Reversal of a LinkedList"
WHY DOES IT MATTER?
In-place reversal is a foundational pattern that demonstrates efficient memory usage and pointer manipulation, skills critical for systems where resources are constrained. It also serves as a building block for more complex list operations such as cycle detection, list partitioning, and merge‑sort on linked lists.
OPTIMIZATION CHALLENGE
The core insight is that you only need to remember the previous node while iterating; by updating the next pointer immediately, you avoid the need for a stack or array, thus reducing space from O(n) to O(1).
REAL-WORLD CONNECTION
Think of a conveyor belt where items (nodes) must be reordered without adding extra storage. Each item is redirected to the previous position by swapping its direction pointer, mirroring how in-place reversal reassigns next references without allocating new nodes.
When explaining this to an interviewer, emphasize the three‑pointer technique and show a quick diagram or mental model of the pointers moving through the list. Highlight that the algorithm is linear and constant‑space, and mention its applicability to other pointer‑heavy problems.
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 in‑place algorithms. The naive approach—collecting all nodes into an auxiliary array or stack and then re‑linking them—requires O(n) extra memory and defeats the purpose of an in‑place transformation. Instead, the optimal paradigm uses three pointers (prev, curr, next) to traverse the list once, reassigning the next reference of each node to point to its predecessor. This single pass algorithm runs in linear time O(n) and constant space O(1), making it ideal for large inputs where memory overhead must be minimized.
The key insight is that each node only needs to know its immediate predecessor after reversal; by updating the next pointer on the fly, we never need to keep the entire list in memory. This approach also preserves the original list structure until the new head is returned, ensuring that no dangling references remain. Because the algorithm is deterministic and uses only a few scalar variables, it scales gracefully to millions of nodes without risking stack overflow or excessive GC pressure.
In interview settings, demonstrating this pattern quickly signals mastery of pointer manipulation, iterative control flow, and space‑time trade‑offs. It also opens the door to related problems such as reversing every k nodes, detecting cycles, or merging sorted lists, all of which rely on similar in‑place techniques.
Interview Questions on This Problem
Q1What is the time and space complexity of reversing a singly linked list in-place, and why is it considered optimal?
The time complexity is O(n) because each node is visited exactly once, and the space complexity is O(1) because only a constant number of pointers are used regardless of list size. This is optimal because any algorithm must at least touch each node to reverse the order, and no additional memory beyond a few variables can be avoided.
Q2How would you modify the in-place reversal algorithm to reverse only the first k nodes of a linked list?
Traverse k nodes while maintaining prev, curr, and next pointers. After the k‑th node, set the next of the original head to point to the (k+1)th node, and set the next of the k‑th node to prev. This yields a reversed segment followed by the untouched remainder.
Q3During an interview, a candidate mistakenly sets curr.next = prev before updating next. What bug does this introduce, and how can it be fixed?
Setting curr.next = prev before storing curr.next in a temporary variable loses the reference to the rest of the list, causing a loss of nodes and potential infinite loops. The fix is to first store next = curr.next, then set curr.next = prev, and finally move curr = next.
Examples
Input
[3, 7, 2, 9]
Output
[9, 2, 7, 3]
Explanation: Start with head → 3 → 7 → 2 → 9 → null. Iterate through the list while re‑linking each visited node to the node processed just before it. After processing 3, the partial reversed list is 3 → null. After processing 7, it becomes 7 → 3 → null. After processing 2, it becomes 2 → 7 → 3 → null. Finally, after processing 9, the list is 9 → 2 → 7 → 3 → null, and 9 is returned as the new head.
Input
[ -5 ]
Output
[ -5 ]
Explanation: A single‑node list is its own reverse. The algorithm visits the only node, points its next to null (which it already is), and returns the same node as the new head.
Input
[10, 20, 30, 40, 50]
Output
[50, 40, 30, 20, 10]
Explanation: Initial list: 10 → 20 → 30 → 40 → 50 → null. The algorithm proceeds as follows: 1. After processing 10: 10 → null. 2. After processing 20: 20 → 10 → null. 3. After processing 30: 30 → 20 → 10 → null. 4. After processing 40: 40 → 30 → 20 → 10 → null. 5. After processing 50: 50 → 40 → 30 → 20 → 10 → null. The final head is the node containing 50.
Constraints
- 1 <= number of nodes <= 10^5
- -2^31 <= node.val <= 2^31 - 1
- The algorithm must use O(1) additional memory besides a few pointer variables.
- The list is singly linked; each node has only a 'next' reference.
Optimal Approach & Strategy
Iteratively traverse the list, reassigning each node’s next pointer to its predecessor using three pointers. This single pass uses only constant extra space.
Brute Force Approach
Collect all nodes in an array, then rebuild the list by linking nodes in reverse order. This uses O(n) extra memory and requires two passes over the data.
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; }class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr) { ListNode* nextTemp = curr->next; curr->next = prev; prev = curr; curr = nextTemp; } return prev; } }class Solution { 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 ListNode: def __init__(self, x): self.val = x; self.next = None; def reverseList(self, head): prev = None; curr = head; while curr: nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; return prevfunction 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.