Watch 10 video solutions for Reverse Linked List, a easy level problem involving Linked List, Recursion. This walkthrough by NeetCode has 670,426 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |