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: Reverse a singly linked list so the tail becomes the new head and every node points to its previous node. You receive the head of the list and must return the new head after reversing all pointers.
Linked lists differ from arrays because nodes are connected by references instead of indices. Reversing the list means walking through each node and redirecting its next pointer. The challenge is doing this without losing access to the remaining nodes while you modify the links. This problem is a core exercise for mastering linked list pointer manipulation.
Approach 1: Iterative Pointer Reversal (O(n) time, O(1) space)
The iterative solution walks through the list once while reversing the direction of every pointer. Maintain three variables: prev, curr, and next. Start with prev = null and curr = head. For each node, temporarily store curr.next in next, set curr.next = prev to reverse the pointer, then advance both pointers forward. This continues until curr becomes null. The last non-null node stored in prev becomes the new head.
The key insight is preserving the next node before modifying the pointer. Without that temporary variable, the rest of the list would be lost. This approach processes each node exactly once, giving O(n) time complexity with O(1) extra space. Most production code uses this version because it is efficient and avoids recursion overhead.
Approach 2: Recursive Reversal (O(n) time, O(n) space)
The recursive method reverses the list from the second node onward, then fixes the first node afterward. Call the function recursively with head.next until reaching the last node, which becomes the new head of the reversed list. During the stack unwind phase, redirect pointers so head.next.next = head and set head.next = null to break the original link.
This approach expresses the reversal elegantly using recursion. Each call handles one node and relies on the rest of the list already being reversed by deeper calls. The algorithm still visits every node once, so time complexity remains O(n). However, the recursion stack stores up to n calls, giving O(n) space complexity. The concept relies on understanding the call stack and is closely related to problems involving recursion.
Recommended for interviews: Interviewers typically expect the iterative solution first because it demonstrates strong control of pointer manipulation and uses constant extra space. Showing the recursive version afterward proves deeper understanding of how linked list operations can be expressed using recursion. Both run in O(n) time, but the iterative approach is usually considered the optimal production implementation.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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) | Best general solution. Efficient pointer manipulation with constant extra memory. |
| Recursive Reversal | O(n) | O(n) | Useful for understanding recursion patterns or when code clarity is preferred over stack usage. |
Reverse Linked List - Iterative AND Recursive - Leetcode 206 - Python • NeetCode • 539,238 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