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
The 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. Then both pointers advance forward, with 'prev' taking the place of 'curr' and 'curr' moving to the next node in the original list. This approach reverses the list in O(n) time and O(1) space.
Optimal Approach
Iterate through the list once, maintaining 'prev' and 'curr' pointers. For each node, store 'curr.next' temporarily, redirect 'curr.next' to 'prev', then move 'prev' and 'curr' forward. When 'curr' becomes None, 'prev' points to the new head of the reversed list, which is returned.
Time
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 |
| 1 | class Solution { |
| 2 | public ListNode reverseList(ListNode head) { |
| 3 | ListNode prev = null; |
| 4 | ListNode curr = head; |
| 5 | |
| 6 | while (curr != null) { |
| 7 | ListNode nextTemp = curr.next; |
| 8 | curr.next = prev; |
| 9 | prev = curr; |
| 10 | curr = nextTemp; |
| 11 | } |
| 12 | |
| 13 | return prev; |
| 14 | } |
| 15 | } |
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
| 5 | while curr:
|
| 6 | next_temp = curr.next
|
| 7 | curr.next = prev
|
| 8 | prev = curr
|
| 9 | curr = next_temp
|
Objective
To reverse the 'next' pointer of each node to point to its predecessor while moving forward through the list.
Key Insight
At each iteration, the algorithm temporarily saves the next node to avoid losing access after reversing the link. Then it redirects 'curr.next' to 'prev', effectively reversing the link. Advancing 'prev' and 'curr' moves the pointers forward, progressively reversing the entire list in a single pass.
Interview Quick-Check
Core Logic
The reversal is done by saving 'curr.next', redirecting 'curr.next' to 'prev', then moving 'prev' and 'curr' forward, ensuring no nodes are lost and all links are reversed.
Common Pitfalls & Bugs
Failing to save 'curr.next' before reassigning it causes loss of the remaining list, breaking traversal.
State & Boundaries
The loop continues until 'curr' becomes None, indicating all nodes have been processed.
Return the New Head of the Reversed List
| 11 | return prev |
Objective
To return the pointer to the new head of the reversed list after traversal completes.
Key Insight
After the loop, 'prev' points to the last processed node, which is the new head of the reversed list. Returning 'prev' provides the caller with the reversed list's entry point.
Interview Quick-Check
Core Logic
Returning 'prev' after the loop completes gives the new head of the reversed list.
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.
prev, curr = None, headInitialize 'prev' to None and 'curr' to the head of the list.
Setting 'prev' to None marks the end of the reversed list, and 'curr' at head starts the traversal from the beginning, enabling in-place reversal without losing nodes.
return prevReturn 'prev' as the new head of the reversed list.
After the loop, 'prev' points to the new head, so returning it provides the reversed list to the caller.
prev = currMove 'prev' forward to the current node.
Advancing 'prev' to 'curr' updates the tail of the reversed portion, preparing for the next reversal step.
curr = next_tempAdvance 'curr' to the next node in the original list.
Moving 'curr' to 'next_temp' continues traversal through the original list, ensuring all nodes are processed.
while curr:Begin loop to process nodes while 'curr' is not None.
The loop condition ensures traversal continues until all nodes have been reversed, guaranteeing a full pass through the list.
Test Your Understanding
Why is it necessary to store 'curr.next' in a temporary variable before redirecting 'curr.next' to 'prev'?
Because once 'curr.next' is redirected to 'prev', the original link to the next node is lost, so storing it temporarily preserves the reference needed to continue traversing the original list.
Related Problems
Linked Lists 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