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 <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
Problem Overview: Given the head of a singly linked list, reverse the list so that the last node becomes the first and every next pointer points to the previous node. Return the new head after reversal. The challenge is pointer manipulation without losing access to the remaining nodes.
Approach 1: Iterative Pointer Reversal (O(n) time, O(1) space)
This approach walks through the list once and reverses the next pointer of every node. Maintain three pointers: prev, curr, and next. For each node, store curr.next in next, redirect curr.next to prev, then advance both pointers forward. The key insight is preserving the next node before modifying the pointer so you never lose the remaining list. After the loop finishes, prev points to the new head of the reversed list. This is the most common solution because it runs in linear time and uses constant extra memory. Problems involving pointer manipulation like this appear frequently in Linked List interview questions.
Approach 2: Recursive Reversal (O(n) time, O(n) space)
The recursive approach reverses the list starting from the second node and fixes the first node during the backtracking phase. Call the recursive function on head.next until the base case (last node) is reached. When the stack unwinds, set head.next.next = head to reverse the pointer direction and then set head.next = null to terminate the list. The recursive call returns the new head, which propagates back through each stack frame. This approach is elegant and highlights how recursion can naturally handle pointer re-linking, but it uses additional call stack space proportional to the list length. It’s a common demonstration of recursion in Recursion and pointer-based structures.
Recommended for interviews: The iterative approach is typically expected because it achieves O(n) time with O(1) extra space and demonstrates strong pointer manipulation skills. Interviewers often accept the recursive version as well, but they may follow up by asking you to reduce space usage. Showing both approaches signals a deeper understanding of how linked list structures work and how pointer direction can be reversed safely.
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.
In this C implementation, three pointers are utilized: prev, curr, and nxt. Initially, prev is NULL while curr points to the head. A loop runs until curr is NULL. Inside the loop, nxt stores the next node, then curr->next is set to prev to reverse the pointer, and prev is moved to curr, curr to nxt.
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.
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.
In the recursive C implementation, the function calls itself with the next node as an argument until it reaches the end of the list. Once there, it starts reversing the pointers. Each function returns the head of the reversed part of the list, making the whole list reversed when it unwinds.
Time Complexity: O(n), due to n recursive calls.
Space Complexity: O(n), for stack space in recursion.
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n), where n is the number of nodes in the linked list because each node is processed once. |
| Recursive Approach | Time Complexity: O(n), due to n recursive calls. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Pointer Reversal | O(n) | O(1) | Preferred solution in interviews and production when constant memory is required |
| Recursive Reversal | O(n) | O(n) | Useful for demonstrating recursion concepts or when recursive style is preferred |
Reverse Linked List - Iterative AND Recursive - Leetcode 206 - Python • NeetCode • 670,426 views views
Watch 9 more video solutions →Practice Reverse Linked List with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor