Reverse Linked List
Problem
Given the head of a singly linked list, reverse the list and return the reversed list.
- The number of nodes in the list is in the range [0, 5000]
- −5000 ≤ Node.val ≤ 5000
Example
head = [1,2,3,4,5][5,4,3,2,1]Starting with the list 1 -> 2 -> 3 -> 4 -> 5, the algorithm iteratively reverses the direction of the 'next' pointers. Initially, 'prev' is None and 'curr' points to the head (1). In the first iteration, the 'next' pointer of node 1 is redirected to None (prev), effectively detaching it from node 2. Then 'prev' moves to node 1, and 'curr' moves to node 2. This process repeats, reversing each link until 'curr' becomes None, indicating the end of the original list. The 'prev' pointer then points to the new head of the reversed list, which is node 5.
Approach
Straightforward Solution
A naive approach might involve creating a new list and copying nodes in reverse order, which uses O(n) extra space and is inefficient.
Core Observation
Reversing a singly linked list in-place requires changing the direction of each node's 'next' pointer so that it points to its predecessor instead of its successor, effectively flipping the list.
Path to Optimal
PreviewThe key insight is to use two pointers, 'prev' and 'curr', to traverse the list once. At each step, the 'next' pointer of 'curr' is redirected to 'prev', reversing the link…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewIterate through the list once, maintaining 'prev' and 'curr' pointers. For each node, store 'curr…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each node is visited exactly once in a single pass through the list, performing constant-time pointer reassignments.
Space
O(1)
Only a fixed number of pointers ('prev', 'curr', 'next_temp') are used, regardless of the list size, so auxiliary space is constant.
Pattern Spotlight
In-place Reversal of a Linked List
Reversing a singly linked list in-place is achieved by iteratively redirecting each node's 'next' pointer to its predecessor while advancing through the list with two pointers, ensuring O(n) time and O(1) space without auxiliary data structures.
Solution
| 1 | class Solution:
|
| 2 | def reverseList(self, head: ListNode) -> ListNode:
|
| 3 | prev, curr = None, head
|
| 4 |
|
| 5 | while curr:
|
| 6 | next_temp = curr.next
|
| 7 | curr.next = prev
|
| 8 | prev = curr
|
| 9 | curr = next_temp
|
| 10 |
|
| 11 | return prev |
Step-by-Step Solution
Initialize Pointers to Start Reversal
| 3 | prev, curr = None, head
|
Objective
To set up the initial state with 'prev' as None and 'curr' pointing to the head of the list.
Key Insight
Starting with 'prev' as None represents the end of the reversed list, and 'curr' at the head allows traversal from the beginning. This setup is essential to iteratively reverse the links without losing track of the list.
Interview Quick-Check
Core Logic
Initializing 'prev' to None marks the new tail of the reversed list, and 'curr' starts the traversal at the original head.
State & Boundaries
If the input list is empty (head is None), the loop is skipped and None is returned immediately.
Iteratively Reverse Links While Traversing the List
To reverse the 'next' pointer of each node to point to its predecessor while moving forward through the list.
Return the New Head of the Reversed List
To return the pointer to the new head of the reversed list after traversal completes.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
curr.next = prevReverse the link by pointing 'curr.next' to 'prev'.
Redirecting 'curr.next' to 'prev' flips the direction of the pointer, which is the fundamental operation that reverses the list in-place.
next_temp = curr.nextTemporarily store the next node after 'curr'.
Saving 'curr.next' before reassigning it preserves access to the remainder of the list, preventing loss of nodes during reversal.
Full line-by-line criticality + rationale for all 7 lines available on Pro.
Test Your Understanding
Why is it necessary to store 'curr.next' in a temporary variable before redirecting 'curr.next' to 'prev'?
See the answer with Pro.
Related Problems
In-place Reversal of a Linked List pattern
Don't just read it. Drill it.
Reconstruct Reverse Linked List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Reverse Linked List drill