Reverse Linked List - Solution & Explanation
Problem Statement
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:
- The number of nodes in the list is the range
[0, 5000]. -5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
Approach Overview
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.
Approach 1: Iterative Approach
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.
Complexity
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.
Approach 2: Recursive Approach
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.
Complexity
Time Complexity: O(n), due to n recursive calls.
Space Complexity: O(n), for stack space in recursion.
Approach 3: Head Insertion Method
We create a dummy node dummy, then traverse the linked list and insert each node after the dummy node. After traversal, return dummy.next.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Approach 4: Recursion
We recursively reverse all nodes from the second node to the end of the list, then attach the head to the end of the reversed list.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the linked list.
Complexity Comparison
| 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. |
| Head Insertion Method | — |
| Recursion | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Reverse Linked List - Iterative AND Recursive - Leetcode 206 - Python • NeetCode • 700,751 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reverse Linked List easy or hard?
Reverse Linked List Python/Java solution
How to solve Reverse Linked List in O(n)?
What is the best approach for Reverse Linked List?
Is Reverse Linked List asked at Google/Amazon/Meta?
What data structure is used in Reverse Linked List?
What is the time complexity of Reverse Linked List?
Ready to solve this problem?
Practice Reverse Linked List with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor