Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2] Output: [2,1]
Example 3:
Input: head = [] Output: []
Constraints:
[0, 5000].-5000 <= Node.val <= 5000Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
The goal of Reverse Linked List is to reverse the direction of pointers in a singly linked list so the head becomes the tail and vice versa. The most common strategy is the iterative pointer manipulation approach. Instead of changing node values, you rewire the next references while traversing the list once. Maintain three pointers: one for the current node, one for the previous node, and one to temporarily store the next node. As you iterate, redirect the next pointer of the current node to the previous node, then move all pointers forward.
Another elegant method uses recursion. The idea is to reverse the rest of the list first and then fix the current node’s pointer during the recursion unwind phase. This approach is conceptually clean but uses the call stack.
The iterative solution runs in O(n) time and O(1) extra space, making it the preferred solution in interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative Pointer Reversal | O(n) | O(1) |
| Recursive Reversal | O(n) | O(n) |
NeetCode
Iterative Approach: This approach involves using a loop to traverse the linked list and reverse the direction of the next pointers at each step. Start with three pointers: prev as null, curr as the head of the list, and nxt to temporarily store the next node. In each iteration, change the curr.next to prev, move prev to curr, and curr to nxt. The loop ends when curr becomes null, with prev being the new head.
Time Complexity: O(n), where n is the number of nodes in the linked list because each node is processed once.
Space Complexity: O(1) as it uses only a constant amount of space.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.
In the Python implementation, prev, curr, and nxt pointers again maintain the structure necessary for iterative reversal. After resetting pointers, the head is reassigned to prev, which is the new head of the reversed list.
Recursive Approach: In this method, you move to the end of the list via recursive calls while reversing the next pointers on the way back. The base case for the recursion is when the list is empty or when it contains only one node. In each call, move to the next node, reverse the rest of the list, use the next pointer's next field to point to the current node, and finally return the head of the reversed list.
Time Complexity: O(n), due to n recursive calls.
Space Complexity: O(n), for stack space in recursion.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Reverse Linked List is a very common interview question at FAANG and other tech companies. It tests fundamental knowledge of linked lists, pointer handling, and basic algorithmic thinking.
Yes, the problem can also be solved recursively. The recursive approach reverses the rest of the list first and then fixes the current node’s pointer, but it uses O(n) stack space due to recursion.
The optimal approach is the iterative pointer reversal method. It traverses the linked list once while adjusting the next pointers, achieving O(n) time complexity and O(1) extra space.
The problem primarily relies on understanding the Linked List data structure and pointer manipulation. Mastering how node references work is key to reversing the list efficiently.
In Java, the recursive function continues traversing until it reaches the list's last node, then starts reversing pointers until reaching the original head. Each recursive call returns the new head of the reversed sublist.